LeetCodeでの0、1、2のソート:効果的なアルゴリズム

問題の要件を満たすために、以下のようないくつかのアプローチがあります。それぞれのアプローチに対して、具体的なコード例を示します。

1. カウントソート: このアプローチでは、まず0、1、2の要素の出現回数を数えます。次に、出現回数に基づいて配列を再構築します。以下にPythonでの実装例を示します。

def sortColors(nums):
    count = [0] * 3
    for num in nums:
        count[num] += 1

    i = 0
    for num in range(3):
        for _ in range(count[num]):
            nums[i] = num
            i += 1

2. 3ポインターアプローチ: このアプローチでは、3つのポインターを使用して、0、1、2の要素を正しい位置に移動します。以下にPythonでの実装例を示します。

def sortColors(nums):
    left = 0
    right = len(nums) - 1
    current = 0

    while current <= right:
        if nums[current] == 0:
            nums[current], nums[left] = nums[left], nums[current]
            left += 1
            current += 1
        elif nums[current] == 2:
            nums[current], nums[right] = nums[right], nums[current]
            right -= 1
        else:
            current += 1

3. 単一パスアルゴリズム: このアプローチでは、1つのポインターを使用して、0、1、2の要素を正しい位置に移動します。以下にPythonでの実装例を示します。

def sortColors(nums):
    left = 0
    right = len(nums) - 1
    current = 0

    while current <= right:
        if nums[current] == 0:
            nums[current], nums[left] = nums[left], nums[current]
            left += 1
            current += 1
        elif nums[current] == 2:
            nums[current], nums[right] = nums[right], nums[current]
            right -= 1
        else:
            current += 1