0075 颜色分类

中等

算法思路

很好奇本题为何不是简单题。在不使用 sort 等内置函数条件下，最直接的方法显然是计数排序，而且性能不弱。

不过，考虑到出题者意图，也可以用双指针完成，这样仅遍历一次数组即可快速实现排序。

代码实现

sort-colors.c

void swap(int* a, int* b) {
    int t = *a;
    *a = *b, *b = t;
}

void sortColors(int* nums, int numsSize) {
    int zero = 0, two = numsSize - 1;
    for (int i = 0; i <= two; i++) {
        if (nums[i] == 0) {
            swap(nums + i, nums + zero);
            zero++;
        } else if (nums[i] == 2) {
            swap(nums + i, nums + two);
            two--;
            i--;
        }
    }
}

• 注意：当遍历到 2 并与后续数字交换时，由于后续数字未知，需要 i-- 重新判断当前索引。