leetcode 색상 분류(분류 처리 이해)

빨간색,흰색,파란색 을 포함 하 는 것 을 지정 합 니 다.모두 n 개의 요소 의 배열 은 제자리 에서 그것들 을 정렬 하여 같은 색채 의 요 소 를 인접 시 키 고 빨간색,흰색,파란색 순서에 따라 배열 한다.
이 문제 에서 우 리 는 정수 0 을 사용한다. 1 과 2 는 각각 빨간색,흰색,파란색 을 나타 낸다.
주의:코드 라 이브 러 리 의 정렬 함 수 를 사용 하여 이 문 제 를 해결 할 수 없습니다.
예시:

  : [2,0,2,1,1,0]
  : [0,0,1,1,2,2]

대부분의 사람들 이 사용 하 는 세 가지 지침 법.
빠 른 배열 의 사상 을 참고 하여 왼쪽 에서 오른쪽으로 스 캔 하고 2 를 배열 오른쪽 에 놓 고 1 을 배열 왼쪽 에 놓는다.세 개의 포인터,하 나 는 배열 의 왼쪽 값,하 나 는 배열 의 오른쪽 값,하 나 는 현재 배열 을 옮 겨 다 니 는 것 을 가리킨다. //현재 값==1 시,cur+.처리 하지 않다. //현재 값==2 시 오른쪽 포인터 와 값 을 교환 합 니 다.오른쪽 포인터--(오른쪽 부분 은 현재 포인터 가 옮 겨 다 니 지 않 은 곳 입 니 다.그 값 은 0,1,2 일 수 있 습 니 다.그래서 현재 cur 지침 은++할 수 없습니다.요소 가 바 뀌 면 이 바 뀐 요 소 를 계속 판단 합 니 다.) //현재 값==0 시,cur++.왼쪽 포인터 와 교환 합 니 다.(왼쪽 부분 은 cur 포인터 가 이미 옮 겨 다 녔 습 니 다.l 포인터 의 값 은 0/1 일 뿐 입 니 다)
성공 하 다.
상세 한 상황 을 나타내다
실행 시간: 1ms,Sort Colors 의 자바 제출 에서 91.02%의 사용 자 를 격파 하 였 습 니 다.
메모리 소모: 35.2 MB,Sort Colors 의 자바 제출 에서 36.68%의 사용 자 를 격파

class Solution {
    public void sortColors(int[] nums) {
        int l = 0;
        int r = nums.length-1;
        int cur = 0;
        while(l 1){
                swap(nums, cur, r--);
            }
            else
                swap(nums, cur++, l++);
        }
    }
    private void swap(int[] data, int i, int j){
        if(i==j)
            return;
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

세 바늘 을 초기 화 할 때 왼쪽 시작 이 0 이 고 오른쪽 끝 이 2 인 경 우 를 건 너 뛰 는 것 을 개선 합 니 다.
성공 하 다.
상세 한 상황 을 나타내다
실행 시간: 1ms,Sort Colors 의 자바 제출 에서 91.02%의 사용 자 를 격파 하 였 습 니 다.
메모리 소모: 34MB,Sort Colors 의 자바 제출 에서 99.82%의 사용 자 를 격파

class Solution {
    public void sortColors(int[] nums) {
        int l = 0;
        int r = nums.length-1;
        int cur = 0;

        while(r>=0 && nums[r] == 2)
                    r--;
        while(l 1)
                swap(nums, cur, r--);
            else
                swap(nums, cur++, l++);
        }
    }
    private void swap(int[] data, int i, int j){
        if(i==j)
            return;
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[못 푼 문제] 백준 10989번

sys.stdin.readline()을 사용하여 input의 시간을 줄였다. 또한 입력 가능한 수의 개수가 10,000,000개 이고 최대 입력 가능한 수가 10,000이기 때문에 모든 수를 입력 받아 리스트로 만들...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

leetcode 색상 분류(분류 처리 이해)

좋은 웹페이지 즐겨찾기