算法课指针] 颜色分类 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 输入 第一行输入一个整数 � ( 1 ≤ � ≤ 3 0 0 ) n (1≤n≤300) 代表数组的长度。 第二行输入一行数字代表数组 � � � � [ � ] nums[i] 为0，1，2，数字与数字之间用空格间开。

这是一道典型的荷兰国旗问题，可以使用三指针的方法解决。具体步骤如下：

1. 定义三个指针，分别指向数组的开始、当前位置和末尾。
2. 遍历数组，如果当前位置为0，则将其与开始指针所指位置交换，并将开始指针后移一位；如果当前位置为2，则将其与末尾指针所指位置交换，并将末尾指针前移一位；如果当前位置为1，则继续遍历。
3. 遍历完成后，数组就被分为了三段，分别为0、1和2。

以下是示例代码实现：

n = int(input())
nums = list(map(int, input().split()))

start, curr, end = 0, 0, n - 1

while curr <= end:
    if nums[curr] == 0:
        nums[start], nums[curr] = nums[curr], nums[start]
        start += 1
        curr += 1
    elif nums[curr] == 2:
        nums[curr], nums[end] = nums[end], nums[curr]
        end -= 1
    else:
        curr += 1

print(nums)

相关问题

用c语言双指针实现，给定一个包含n+1个整数的数组nums，其数字都在[1,n]范围内（包括1和n），可知至少存在一个重复的整数，假设nums只有一个重复整数，返回这个重复整数

在C语言中，可以使用双指针技巧（也称为快慢指针）来解决这个问题。这种算法通常用于查找数组中的重复元素，因为它的效率较高。以下是基本步骤：

1. 定义两个指针，`left` 和 `right`，分别初始化为数组的开始和结束。

2. `left` 指针指向第一个元素，`right` 指针指向最后一个元素。

3. 使用一个 while 循环，当 `left` < `right` 时，执行以下操作：
a. 计算当前两个指针所指向元素的差值，并取模 n+1（这是因为数组元素范围是从 1 到 n 的整数）。如果它们的余数相等，说明找到了重复的数字（因为 (a - b) % (n+1) 相同意味着 a 和 b 同时除以 n+1 的余数相同，而由于 n+1 是唯一的重复元素的倍数，所以能确定 a 和 b 有相同的原数值）。
b. 如果余数不相等，将较小的余数对应的元素移动到 `left`（即如果 `(nums[left] - nums[right]) % (n+1)` 小，则更新 `left = left + 1`；反之则 `right = right - 1`），继续比较。

4. 当 `left` 和 `right` 相遇时，`nums[left]` 就是重复的那个数字。

下面是一个简单的伪代码示例：

int findDuplicate(int* nums, int n) {
    int left = 0, right = n;
    while (left < right) {
        if (nums[left] != nums[left % (n + 1)]) {
            left++;
        } else {
            right--;
        }
    }
    return nums[left];
}

给定一个升序排列的数组 nums，请原地删除重复出现的元素

如果要在原地删除重复出现的元素，可以使用双指针法。首先，初始化两个指针 i 和 j，其中 i 是慢指针，j 是快指针。然后，遍历数组，如果 nums[i] 等于 nums[j]，则递增 j，直到 nums[j] 不等于 nums[i]。接着，将 nums[j] 赋值给 nums[i+1]，并递增 i。重复上述过程，直到遍历完整个数组。

例如，给定数组 [0,0,1,1,1,2,2,3,3,4]，则原地删除重复出现的元素后，数组变为 [0,1,2,3,4]，并返回新数组的长度 5。

算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例代码（使用 Python 语言）如下：

def removeDuplicates(nums):
    if not nums:
        return 0

    i = 0
    for j in range(1, len(nums)):
        if nums[i] != nums[j]:
            i += 1
            nums[i] = nums[j]

    return i + 1