面试题 10.01. 合并排序的数组 - 力扣LeetCode方法一直接合并后排序最先想到的一种方法也是最基础、最直接的方法就是将B中的数据追加到A数组中然后排序。如下代码首先将B中的数据追加到A的后边然后使用堆排序进行排序。时间复杂度O((mn)log(mn))空间复杂度O(1)直接在数组A上进行排序没有使用新的空间。class Solution { public: void merge(vectorint A, int m, vectorint B, int n) { for (int i 0; i n; i) { A[mi] B[i]; } heapSort(A, mn); } void heapSort(vectorint data, int size) { makeInitialHeap(data, size); for (int i 0; i size; i) { int tmp data[0]; data[0] data[size - 1 - i]; data[size - 1 - i] tmp; adjustHeap(data, 0, size - 1 - i - 1); } } void makeInitialHeap(vectorint data, int size) { int mid size / 2; for (int i mid; i 0; i--) { adjustHeap(data, i, size - 1); } } //调整堆使用递归算法 //调整堆是堆排序的核心算法 void adjustHeap(vectorint data, int startIndex, int endIndex) { if (startIndex endIndex) { return; } int leftChildIndex startIndex * 2 1; int rightChildIndex startIndex * 2 2; int biggerIndex startIndex; if (leftChildIndex endIndex data[leftChildIndex] data[biggerIndex]) { biggerIndex leftChildIndex; } if (rightChildIndex endIndex data[rightChildIndex] data[biggerIndex]) { biggerIndex rightChildIndex; } if (biggerIndex ! startIndex) { int tmp data[startIndex]; data[startIndex] data[biggerIndex]; data[biggerIndex] tmp; adjustHeap(data, biggerIndex, endIndex); } } };方法二双指针利用A和B已是排序链表的前提使用双指针进行排序。时间复杂度O(mn)空间复杂度O(mn)。class Solution { public: void merge(vectorint A, int m, vectorint B, int n) { vectorint tmp(mn); int index 0; int i 0; int j 0; while (i m j n) { if(A[i] B[j]) { tmp[index] A[i]; index; i; } else { tmp[index] B[j]; index; j; } } while (i m) { tmp[index] A[i]; index; i; } while (j n) { tmp[index] B[j]; index; j; } for (int k 0; k m n; k) { A[k] tmp[k]; } } };双指针的思想在一些题目中也会被用到①回文字符串需要使用双指针两个指针从两边向中间进行字符对比②环形链表使用快慢指针快慢指针也属于双指针③在快速排序中首先要选定一个值然后要确定这个值在数组中的位置也需要从左和从右向中间进行比较也会用到双指针方法三从后向前方法二中使用了一个临时数组先将数据放到临时数组中排序完成之后再将数据放回数组A中。之所以使用临时数组是因为如果直接将数据放到数组A中可能会出现数据被覆盖的情况。为了避免数据被覆盖的情况可以使用一个临时数组还可以使用从后向前的方法。class Solution { public: void merge(vectorint A, int m, vectorint B, int n) { int i m - 1; int j n - 1; int index m n - 1; while (i 0 j 0) { if (A[i] B[j]) { A[index] A[i]; index--; i--; } else { A[index] B[j]; index--; j--; } } while(j 0) { A[index] B[j]; index--; j--; } } };从前向后是我们默认的最自然的一种方式。有时候从前向后不是最优解需要使用从后向前的方式。内存移动的实现也用到了从后向前的方法。数据的长度是n从源地址src移动到目的地址dst有以下4种情况1src和dst没有重合src在dst前边。可以从前向后移动也可以从后向前移动。2src和dst有重合src在dst前边。从前向后移动会出现覆盖的情况只能从后向前移动。3src和dst有重合src在dst后边。可以从前向后移动从后向前移动会出现覆盖的情况。4src和dst没有重合src在dst后边。可以从前向后移动也可以从后向前移动。可以使用if else来实现共4个分支。4个判断分支还可以优化4种分类情况可以分为两类主要是情况2和情况3两类情况1和情况2可以属于其中的一类。如下代码将2和1划分到了同一类3和4划分到了同一类。void *memmove(void *dst,const void *src,int n) { char *dp (char *)dst; char *sp (char *)src; if (sp dp){ for (int i 0; i n; i) { *(dp n - 1 - i) *(sp n - 1 - i); } } else { for (int i 0; i n; i) { *(dp i) *(sp i) } } } return dst; }
面试题 10.01. 合并排序的数组 - 力扣LeetCode方法一直接合并后排序最先想到的一种方法也是最基础、最直接的方法就是将B中的数据追加到A数组中然后排序。如下代码首先将B中的数据追加到A的后边然后使用堆排序进行排序。时间复杂度O((mn)log(mn))空间复杂度O(1)直接在数组A上进行排序没有使用新的空间。class Solution { public: void merge(vectorint A, int m, vectorint B, int n) { for (int i 0; i n; i) { A[mi] B[i]; } heapSort(A, mn); } void heapSort(vectorint data, int size) { makeInitialHeap(data, size); for (int i 0; i size; i) { int tmp data[0]; data[0] data[size - 1 - i]; data[size - 1 - i] tmp; adjustHeap(data, 0, size - 1 - i - 1); } } void makeInitialHeap(vectorint data, int size) { int mid size / 2; for (int i mid; i 0; i--) { adjustHeap(data, i, size - 1); } } //调整堆使用递归算法 //调整堆是堆排序的核心算法 void adjustHeap(vectorint data, int startIndex, int endIndex) { if (startIndex endIndex) { return; } int leftChildIndex startIndex * 2 1; int rightChildIndex startIndex * 2 2; int biggerIndex startIndex; if (leftChildIndex endIndex data[leftChildIndex] data[biggerIndex]) { biggerIndex leftChildIndex; } if (rightChildIndex endIndex data[rightChildIndex] data[biggerIndex]) { biggerIndex rightChildIndex; } if (biggerIndex ! startIndex) { int tmp data[startIndex]; data[startIndex] data[biggerIndex]; data[biggerIndex] tmp; adjustHeap(data, biggerIndex, endIndex); } } };方法二双指针利用A和B已是排序链表的前提使用双指针进行排序。时间复杂度O(mn)空间复杂度O(mn)。class Solution { public: void merge(vectorint A, int m, vectorint B, int n) { vectorint tmp(mn); int index 0; int i 0; int j 0; while (i m j n) { if(A[i] B[j]) { tmp[index] A[i]; index; i; } else { tmp[index] B[j]; index; j; } } while (i m) { tmp[index] A[i]; index; i; } while (j n) { tmp[index] B[j]; index; j; } for (int k 0; k m n; k) { A[k] tmp[k]; } } };双指针的思想在一些题目中也会被用到①回文字符串需要使用双指针两个指针从两边向中间进行字符对比②环形链表使用快慢指针快慢指针也属于双指针③在快速排序中首先要选定一个值然后要确定这个值在数组中的位置也需要从左和从右向中间进行比较也会用到双指针方法三从后向前方法二中使用了一个临时数组先将数据放到临时数组中排序完成之后再将数据放回数组A中。之所以使用临时数组是因为如果直接将数据放到数组A中可能会出现数据被覆盖的情况。为了避免数据被覆盖的情况可以使用一个临时数组还可以使用从后向前的方法。class Solution { public: void merge(vectorint A, int m, vectorint B, int n) { int i m - 1; int j n - 1; int index m n - 1; while (i 0 j 0) { if (A[i] B[j]) { A[index] A[i]; index--; i--; } else { A[index] B[j]; index--; j--; } } while(j 0) { A[index] B[j]; index--; j--; } } };从前向后是我们默认的最自然的一种方式。有时候从前向后不是最优解需要使用从后向前的方式。内存移动的实现也用到了从后向前的方法。数据的长度是n从源地址src移动到目的地址dst有以下4种情况1src和dst没有重合src在dst前边。可以从前向后移动也可以从后向前移动。2src和dst有重合src在dst前边。从前向后移动会出现覆盖的情况只能从后向前移动。3src和dst有重合src在dst后边。可以从前向后移动从后向前移动会出现覆盖的情况。4src和dst没有重合src在dst后边。可以从前向后移动也可以从后向前移动。可以使用if else来实现共4个分支。4个判断分支还可以优化4种分类情况可以分为两类主要是情况2和情况3两类情况1和情况2可以属于其中的一类。如下代码将2和1划分到了同一类3和4划分到了同一类。void *memmove(void *dst,const void *src,int n) { char *dp (char *)dst; char *sp (char *)src; if (sp dp){ for (int i 0; i n; i) { *(dp n - 1 - i) *(sp n - 1 - i); } } else { for (int i 0; i n; i) { *(dp i) *(sp i) } } } return dst; }
