首页 > 代码库 > 【leetcode】Sort Colors(middle)☆
【leetcode】Sort Colors(middle)☆
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
颜色排序
思路：
直觉看一定有简单的方法的，可惜我没想出来，就复习一下二分归并排序吧。
void sortColors(int A[], int n) { MergeSort(A, 0, n - 1); } void MergeSort(int A[], int l, int r) { if(l < r) { int mid = (l + r) / 2; MergeSort(A, l, mid); MergeSort(A, mid + 1, r); Merge(A, l, mid, r); } } void Merge(int A[], int l, int mid, int r) { int x = mid - l + 1; int y = r - mid; int * B = new int[x]; int * C = new int[y]; memcpy(B, A + l, x * sizeof(int)); memcpy(C, A + mid + 1, y * sizeof(int)); int i = 0, j = 0, k = l; while(i < x && j < y) { if(B[i] < C[j]) A[k] = B[i++]; else A[k] = C[j++]; k++; } if(i >= x) memcpy(A + k, C + j, (y - j) * sizeof(int)); else memcpy(A + k, B + i, (x - i) * sizeof(int)); delete [] B; delete [] C; }
看看大神的线性时间、常量空间的方法
①说实话，我一眼望过去看不懂啊。研究了半天，发现 n0是最后一个0个位置， n1是最后一个1的位置， n2是最后一个2的位置
每次新来一个0，需要依次把2、1向后延1位。
就是2先向后多占一个位置，然后1向后多占一个位置，把2最前面的给覆盖，0再多占一个位置，新加的0覆盖了1最前面多出来的。
依此类推。
void sortColors2(int A[], int n) { int n0 = -1, n1 = -1, n2 = -1; for (int i = 0; i < n; ++i) { if (A[i] == 0) { A[++n2] = 2; A[++n1] = 1; A[++n0] = 0; } else if (A[i] == 1) { A[++n2] = 2; A[++n1] = 1; } else if (A[i] == 2) { A[++n2] = 2; } }
【leetcode】Sort Colors(middle)☆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。