力扣75题 解题思路和步骤 C++代码实现,力扣358题

一、问题背景与初步理解

力扣第75题是一道经典的排序问题，要求对数组中的元素按照特定的规则进行分类。题目中给定一个数组，其中每个元素代表红、白、蓝三种颜色，分别用数字0、1、2表示。目标是将数组重新排列，使得所有0排在最前面，所有1排在中间，所有2排在面。这个问题的背景来源于荷兰国旗问题，因此也被称为荷兰国旗问题。解决这一问题的关键在于设计一种高效的方法，能够在不使用额外空间的情况下完成分类任务。

在接下来的内容中，我们将详细讨论如何通过双指针法来解决该问题。

二、算法设计与实现步骤

双指针法是一种非常有效的解决方法，其核心思想是通过两个指针分别标记当前处理的位置以及需要交换的目标位置。定义两个指针left和right，分别指向数组的起始位置和结束位置。另一个指针current用于遍历整个数组。当current指向的元素为0时，将其与left指针指向的元素交换，并移动left和current指针；当current指向的元素为2时，将其与right指针指向的元素交换，并移动right指针；当current指向的元素为1时，仅移动current指针。

这种策略能够保证在一次遍历过程中完成数组的分类。

三、复杂度分析与优化建议

算法的时间复杂度为O(n)，空间复杂度为O(1)，非常适合大规模数据处理。进一步优化可以通过减少不必要的交换操作来提升性能，在某些情况下提前终止循环。

四、代码实现

void sortColors(vector& nums) {
    int left = 0, right = nums.size() - 1;
    int current = 0;
    while (current <= right) {
        if (nums[current] == 0) {
            swap(nums[current], nums[left]);
            left++;
            current++;
        } else if (nums[current] == 2) {
            swap(nums[current], nums[right]);
            right--;
        } else {
            current++;
        }
    }
}

int main() {
    vectornums = {2, 0, 1, 2, 1, 0};
    sortColors(nums);
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}