[LeetCode] 075. Sort Colors

https://leetcode.com/problems/sort-colors/

Sort Colors - LeetCode

 

1. Selection Sort

    vector<int> sortColors(vector<int>& nums) {
        for(int i=0; i<nums.size(); ++i)
        {
            int min_idx = i;
            for(int j=i+1; j<nums.size();++j)
                if(nums[j] < nums[min_idx])
                    min_idx = j;
            
            swap( nums[i], nums[min_idx]);
        }
        return nums;
    }

 

2. Three Pointer

vector<int> sortColors(vector<int>& nums) {
    int low,mid;
    low = mid = 0;
    int high = nums.size()-1;

    while(mid<=high)
    {
        if( nums[mid] == 0)
        {
            swap(nums[low], nums[mid]);
            low++;
            mid++;
        }
        else if( nums[mid] == 1 )
        {
            mid++;
        }
        else if(nums[mid]==2)
        {
            swap(nums[mid], nums[high]);
            high--;
        }
    }
    return nums;
}

  0, 1, 2 세 숫자만 사용하고 있다. 배열을 3구역으로 나누어 저장하면 된다. low, mid, high. low에 0만 들어가고, mid에 1만 들어가고, high에 2만 들어간다. 이때 low, mid, high를 index로 표기한다. low 혹은 high에 값이 들어가면 다음 index로 넘어가서 입력받을 준비를 한다.

 low index가 업데이트 될 때 mid index가 함께 업데이트 된다. mid index가 low index보다 뒤쳐지면 mid[index] 값이 항상 0이된다.

  값이 1일 때 mid index 홀로 업데이트 되는 이유는 후에 low index로 값을 조정해줘야 할 경우가 생기기 때문이다.

 

3. Count

    vector<int> sortColors(vector<int>& nums) {
        int num0 = 0, num1 = 0, num2 = 0;

        for(int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) ++num0;
            else if (nums[i] == 1) ++num1;
            else if (nums[i] == 2) ++num2;
        }

        for(int i = 0; i < num0; ++i) nums[i] = 0;
        for(int i = 0; i < num1; ++i) nums[num0+i] = 1;
        for(int i = 0; i < num2; ++i) nums[num0+num1+i] = 2;

        return nums;
    }

몇 개인지 셀 수 있다. 참신