Lintcode: Sort Colors II
Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k. Note You are not suppose to use the library's sort function for this problem. Example GIven colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4]. Challenge A rather straight forward solution is a two-pass algorithm using counting sort. That will cost O(k) extra memory. Can you do it without using extra memory?
先写了个O(kN)时间复杂度,O(1)空间复杂度的, 这个算法适合颜色数比较少的情况(k is constant)
1 class Solution { 2 /** 3 * @param colors: A list of integer 4 * @param k: An integer 5 * @return: nothing 6 */ 7 public void sortColors2(int[] colors, int k) { 8 // write your code here 9 if (colors==null || colors.length==0 || k<=1) return; 10 int l=0, r=colors.length-1; 11 int cnt = 1; 12 for (; cnt<k; cnt++) { 13 while (true) { 14 while (l<r && colors[l]==cnt) { 15 l++; 16 } 17 while (l<r && colors[r]!=cnt) { 18 r--; 19 } 20 if (l == r) break; 21 swap(colors, l, r); 22 } 23 r = colors.length-1; 24 if (l == r) break; 25 } 26 } 27 28 public void swap(int[] colors, int l, int r) { 29 int temp = colors[l]; 30 colors[l] = colors[r]; 31 colors[r] = temp; 32 } 33 }
K->N的话,上面时间复杂度就大了,所以干脆用Quick Sort
1 class Solution { 2 /** 3 * @param colors: A list of integer 4 * @param k: An integer 5 * @return: nothing 6 */ 7 public void sortColors2(int[] colors, int k) { 8 // write your code here 9 if (colors==null || colors.length==0 || k<=1) return; 10 quickSort(colors, 0, colors.length-1); 11 } 12 13 public void quickSort(int[] colors, int l, int r) { 14 if (l >= r) return; 15 int pivot = r; 16 int pos = partition(colors, l, r, pivot); 17 quickSort(colors, l, pos-1); 18 quickSort(colors, pos+1, r); 19 } 20 21 public int partition(int[] colors, int start, int end, int pivot) { 22 int l=start, r=end; 23 while (true) { 24 while (l<r && colors[l]<colors[pivot]) { 25 l++; 26 } 27 while (l<r && colors[r]>=colors[pivot]) { 28 r--; 29 } 30 if (l == r) break; 31 swap(colors, l, r); 32 } 33 swap(colors, l, end); 34 return l; 35 } 36 37 public void swap(int[] colors, int l, int r) { 38 int temp = colors[l]; 39 colors[l] = colors[r]; 40 colors[r] = temp; 41 } 42 }
有人给出了O(N)的解法(better solution)
inplace,并且O(N)时间复杂度的算法。
O(n): use the array itself as space to store counts. We use A[k-1] to store the count of color k. We use negtive number to store count, in order to be distnct with the color value. This method ASSUMES that every color between 1 and k will appear.
At position i, if A[i] is positive, we check the value of A[A[i]-1], if it is a positive number, i.e., not counted yet, we then put A[A[i]-1] to A[i], and set A[A[i]-1] as -1 to indicate that there is one of this color.
If A[A[i]-1] is a negtive or zero value, we then simply decrease it by one and set A[i] as 0 to indicate that this position is couted already.
At position i, we repeat this procedure until A[i] becomes 0 or negtive, we then move to i+1.
At counting, we draw colors into array.
3 2 2 1 4
2 2 -1 1 4
2 -1 -1 1 4
0 -2 -1 1 4
-1 -2 -1 0 4
-1 -2 -1 -1 0
1 class Solution { 2 /** 3 * @param colors: A list of integer 4 * @param k: An integer 5 * @return: nothing 6 */ 7 public void sortColors2(int[] colors, int k) { 8 //The method assumes that every color much appear in the array. 9 int len = colors.length; 10 if (len<k) return; 11 12 //count the number of each color. 13 for (int i=0;i<len;i++){ 14 while (colors[i]>0){ 15 int key = colors[i]-1; 16 if (colors[key]<=0){ 17 colors[key]--; 18 colors[i]=0; 19 } 20 else { 21 colors[i] = colors[key]; 22 colors[key] = -1; 23 } 24 } 25 } 26 27 //draw colors. 28 int index = len - 1; 29 for (int i = k - 1; i >= 0; i--) { 30 int cnt = -colors[i]; 31 32 // Empty number. 33 if (cnt == 0) { 34 continue; 35 } 36 37 while (cnt > 0) { 38 colors[index--] = i + 1; 39 cnt--; 40 } 41 } 42 } 43 }
若k事先不知道,一样的,就是开始维护一个counter, 在过程中算一下。
1 class Solution { 2 /** 3 * @param colors: A list of integer 4 * @param k: An integer 5 * @return: nothing 6 */ 7 public void sortColors2(int[] colors) { 8 // write your code here 9 int len = colors.length; 10 11 int count = 0; 12 for (int i=0; i<len; i++) { 13 while (colors[i] > 0) { 14 count++; 15 int pos = colors[i]-1; //最好搞个变量存一下,之后方便 16 if (colors[pos] > 0) { 17 colors[i] = colors[pos]; 18 colors[pos] = -1; 19 } 20 else { 21 colors[pos]--; 22 colors[i] = 0; 23 } 24 } 25 } 26 27 //sort 28 int index = colors.length-1; 29 for (int j=count; j>0; j--) { 30 int num = -colors[j-1]; 31 while (num > 0) { 32 colors[index--] = j; 33 num--; 34 } 35 } 36 } 37 }
相关文章
- leetcode笔记:Ugly Number II
- leetcode第一刷_Subsets II
- 【Luogu1414】又是毕业季II(数论)
- Scrapy研究探索(六)——自己主动爬取网页之II(CrawlSpider)
- leetCode 45.Jump Game II (跳跃游戏) 解题思路和方法
- HDU 2639 Bone Collector II
- 力扣解法汇总998-最大二叉树 II
- 多目标遗传算法 ------ NSGA-II (部分源码解析) 目标函数值计算 eval.c
- 重构-使代码更简洁优美II:实际经验之谈(项目分层是怎么扯上代码节省的)
- [LintCode] Best Time to Buy and Sell Stock II 买股票的最佳时间之二
- [LintCode] Wiggle Sort II 扭动排序之二
- [CareerCup] 15.2 Renting Apartment II 租房之二
- [LeetCode] Wiggle Sort II 摆动排序之二
- [LeetCode] 264. Ugly Number II 丑陋数之二
- 451. Sort Characters By Frequency (sort map)
- 324. Wiggle Sort II