Sorted Array II Leetcode 솔루션에서 중복 제거

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple Facebook 구글 Microsoft
배열 두 포인터조회수 55

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 설명 :

정수가 주어짐 정렬 정렬된 숫자의 감소하지 않는 차수, 일부 중복 제거 그 자리에 각각의 고유한 요소가 나타나도록 최대 두 번. 그만큼 상대적 순서 요소의 유지해야 같은.

일부 언어에서는 배열의 길이를 변경하는 것이 불가능하기 때문에 대신 결과를 다음 위치에 배치해야 합니다. 첫 번째 부분 배열 번호의. 더 공식적으로, 중복을 제거한 후 k 요소가 있는 경우 nums의 처음 k 요소가 최종 결과를 보유해야 합니다. 처음 k개 요소를 넘어 무엇을 남겨두는지는 중요하지 않습니다.

리턴 k 최종 결과를 첫 번째에 배치한 후 k 슬롯 숫자.

Do 지원 다른 어레이에 추가 공간을 할당하십시오. 다음을 수행해야 합니다. 입력 배열 수정 그 자리에 O(1) 추가 메모리 포함.

사용자 정의 판사:

판사는 다음 코드를 사용하여 솔루션을 테스트합니다.

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

모든 어설션이 통과되면 솔루션은 다음과 같습니다. 접수.

예 :

예제 1 

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

예제 2 

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

제약:

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.

직관:

  • 배열이기 때문에 분류, 모든 복제본은 연속적인. 그래서 우리는 사용할 수 있습니다 두 포인터 알고리즘.
  • 하나의 포인터는 nums 배열을 반복합니다. 즉 itr 그리고 다른 즉 길이 동일한 nums 배열의 인덱스를 가리키지만 이 길이 인덱스 이전에 nums의 모든 요소 수는 2보다 크지 않습니다.

알고리즘 :

  • 가변 길이를 가져 와서 요소의 0 번째 인덱스에 있는 요소를 가리킵니다. 배열 번호.
  • 변수를 가져 가라 countElement 초기화 그것과 함께 1 우리는 이미 탈출하고 있기 때문에 0번째 인덱스.
  • 변수를 가져 가라 itr초기화 그것과 함께 1, 같이 itr 반복할 것이다 nums.
  • If nums[itr]==nums[itr-1]countElement ~보다 작다. 2 그런 다음 요소를 넣을 수 있습니다. 숫자[itr] 길이의 위치에 넣은 후 증가 길이 변수.
  • 그렇지 않으면 nums[itr] !=nums[itr-1] 그런 다음 nums[itr]은 새 요소이므로 다시 카운트 요소 될거야  1와 같다.,
  • 마지막으로 반환 길이+1 길이를 인덱스로 사용하고 길이를 반환해야 합니다.
  • 더 나은 이해를 위해 코드를 살펴보십시오.

정렬된 배열 II에서 중복 제거 코드:

Sorted Array II Leetcode Java 솔루션에서 중복 제거:

class Solution {
    public int removeDuplicates(int[] nums) {
        int n=nums.length;
        int itr=1;
        int length=0;
        int countElement =1;
        while(itr<n){
            if(nums[itr]==nums[itr-1]){
                if(countElement<2){
                    countElement++;
                    length++;
                    nums[length]=nums[itr];
                }  
            }
            else{
                countElement=1;
                length++;
                nums[length]=nums[itr];
            }
           itr++; 
        }
        return length+1;
    }
}

Sorted Array II Leetcode C++ 솔루션에서 중복 제거:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
         int n=nums.size();
        int itr=1;
        int length=0;
        int countElement =1;
        while(itr<n){
            if(nums[itr]==nums[itr-1]){
                if(countElement<2){
                    countElement++;
                    length++;
                    nums[length]=nums[itr];
                }  
            }
            else{
                countElement=1;
                length++;
                nums[length]=nums[itr];
            }
           itr++; 
        }
        return length+1;
    }
};

Sorted Array II에서 중복 제거를 위한 복잡성 분석:

시간 복잡성

위 코드의 시간 복잡성은 의 위에) N = 입력 배열의 크기인 최악의 경우 전체 입력 배열을 한 번 탐색하기 때문입니다.

공간 복잡성 

위 솔루션의 공간 복잡도는 O (1) 우리가 사용하고 있기 때문에 일정한 추가 공간.

균열 시스템 설계 인터뷰
Translate »