arrays - 力扣代码 : sort an array of n objects with k different colors

Question

我的输出是 [1, 2, 2, 4, 3]，不对。它应该是 [1, 2, 2, 3, 4]。但是我在我的代码中找不到错误。谁能帮我找出算法的错误？谢谢。我的整个代码复制在下面。可以实现。

问题:

给定一个包含 n 个具有 k 种不同颜色(从 1 到 k 编号)的对象的数组，对它们进行排序，使相同颜色的对象相邻，颜色的顺序为 1、2、... k。

例子:给定 colors=[3, 2, 2, 1, 4], k=4，您的代码应该将颜色就地排序为 [1, 2, 2, 3, 4]。

要求:一个相当直接的解决方案是使用计数排序的两次通过算法。这将花费 O(k) 额外的内存。你能在不使用额外内存的情况下做到吗？

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);
   }
}

Answer 1

您的最小/最大搜索排除了最后一个元素。使用包含上限:

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