企业官网建设流程全解析

面试题 10.01. 合并排序的数组 - 力扣（LeetCode）

方法一：直接合并后排序

最先想到的一种方法，也是最基础、最直接的方法，就是将B中的数据追加到A数组中，然后排序。如下代码，首先将B中的数据追加到A的后边，然后使用堆排序进行排序。

时间复杂度O((m+n)log(m+n))；空间复杂度O(1)，直接在数组A上进行排序，没有使用新的空间。

class Solution { public: void merge(vector<int>& A, int m, vector<int>& B, int n) { for (int i = 0; i < n; i++) { A[m+i] = B[i]; } heapSort(A, m+n); } void heapSort(vector<int>& 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(vector<int>& data, int size) { int mid = size / 2; for (int i = mid; i >= 0; i--) { adjustHeap(data, i, size - 1); } } //调整堆，使用递归算法 //调整堆是堆排序的核心算法 void adjustHeap(vector<int>& 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(m+n)，空间复杂度O(m+n)。

class Solution { public: void merge(vector<int>& A, int m, vector<int>& B, int n) { vector<int> tmp(m+n); 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(vector<int>& A, int m, vector<int>& 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; }