Sort Colors II in Java : a little error in the output, but can not find out why


  • 0
    W

    My output is [1, 2, 2, 4, 3], not right. It should be [1, 2, 2, 3, 4]. But I can't find the error in my code. Could anyone help me find out the error of algorithm ? Thank you. My entire code is copied below. It can be implemented.

    The completer Question is :

    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.

    Example: Given colors=[3, 2, 2, 1, 4enter code here], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].

    Requirements: 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?

    import java.util.Arrays;
    
    public class SortColorsII {
    	public static void sortColors2(int[] colors, int k) {  
    		int count = 0;  
            int start = 0;  
            int end = colors.length-1;  
            while (count <= k) {  
                int min = Integer.MAX_VALUE;  
                int max = Integer.MIN_VALUE;  
                  
                for (int i = start; i < end; i++) {  
                    min = Math.min(min, colors[i]);  
                    max = Math.max(max, colors[i]);  
                }  
                int left = start;  
                int right = end;  
                int cur = left;  
                while(cur <= right) {  
                    if (colors[cur] == min) {  
                        swap(left, cur, colors);  
                        cur++;  
                        left++;  
                    } else if(colors[cur] == max) {  
                    	swap(cur, right, colors);  
                        right--;  
                    } else {  
                        cur++; 
                    }  
                }  
                count += 2;  
                start = left;  
                end = right;  
            }  
    	}  
    	  
    	private static void swap(int left, int right, int[] colors) {  
    	    int tmp = colors[left];  
    	    colors[left] = colors[right];  
    	    colors[right] = tmp;  
    	} 
    	public static void main(String[] args){
    		int[] colors = new int[]{3, 2, 2, 1, 4};
    		int k = 4;
    		sortColors2(colors,  k);
    		String res = Arrays.toString(colors);
    		System.out.println(res);
    	}
    
    }

  • 0
    W

    I found my error. The minimum/maximum search excludes the last element. Change to use an inclusive upper bound:

    for (int i = start; i <= end; i++) 

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.