시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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) 우리가 사용하고 있기 때문에 일정한 추가 공간.
