sort-colors-ii

936 단어
n개의 대상(k종의 다른 색을 포함하고 1~k에 따라 번호를 매긴다)이 있는 그룹을 지정하여 대상을 분류하여 같은 색의 대상을 인접시키고 1,2에 따라...k의 순서로 정렬하다.
예제
colors=[3, 2, 2, 1, 4],k=4,당신의 코드는 제자리에서 조작해서 그룹을 [1, 2, 2, 3, 4]로 만들어야 합니다.
주의
코드 라이브러리의 정렬 함수를 사용하여 이 문제를 해결할 수 없습니다. 추가 공간을 사용하지 않습니다.
class Solution{
public:
    void sortColors2(vector<int> &colors, int k) {
        int n=colors.size();
        if(n<=1) return;        
        helper(colors,0,n-1,1,k);
    }
    void helper(vector<int>&colors,int low,int high,int min,int max){
        if(min>=max) return;
        int left=low,right=high;
        int i=left;
        while(i<=right){
            if(colors[i]==min) swap(colors[i++],colors[left++]);
            else if(colors[i]==max) swap(colors[i],colors[right--]);
            else i++;
        }
        helper(colors,left,right,min+1,max-1);
    }
};

좋은 웹페이지 즐겨찾기