시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
흔들기 정렬!?
내 모든 독자들은 오늘의 문제의 이름이 매우 재미 있다는 것을 알았을 것입니다. 그러나 다양한 범위의 개념에 대한 우리의 이해를 테스트하는 것은 매우 현명한 문제입니다.
더 이상 혼동하지 않고 문제로 바로 넘어 갑시다.
차례
예
당신은 배열이 있습니다
입력 : [1,5,1,6,4]
예상 출력 : [1,6,4,1,5]
어떻게?
흔들림도 정렬 :
배열의 요소는 다음과 같이 정렬되어야합니다. arr[0]<arr[1]>arr[2]<arr[3]
등등 흔들림 정렬에서.
접근
가장 쉬운 방법으로 갈 것입니다. 다음 예를 고려하여
배열 : [1,5,1,1,6,4]
해당 배열의 복사본을 만들어 정렬하겠습니다.
파란색 : 원래 배열 빨간색 : 정렬 됨 배열 복사
어레이 길이 : 6
복사 배열의 작은 요소를 원래 배열에 배치하겠습니다.
작은 요소를 복사 한 후 원래 배열
지금. 남은 부분에 더 큰 요소를 배치하겠습니다.
짜잔. 배열이 흔들려 정렬되었습니다!
홀수 요소를 포함하는 배열에 대해 패스를 약간 변경합니다.
살펴 보겠습니다.
두 번째 마지막 요소 대신 마지막 요소에서 시작합니다.
첫 번째 패스 후
이제 더 큰 요소를
A 비슷한 문제 우리는 좋은 이해를 얻기 위해 우리와 함께 확인할 수 있습니다.
이제 우리는 그것을 이해했습니다. 코드를 살펴 보자
흔들기 정렬을위한 Java 코드
class Solution { int index=0; public void assemble(int[] nums,int copy[],int start) { //The assemble function for(int i=start;i>-1;i=i-2) { nums[i]=copy[index]; index++; } } public void wiggleSort(int[] nums) { int copy[]=new int[nums.length]; for(int i=0;i<nums.length;i++) copy[i]=nums[i]; Arrays.sort(copy); if(nums.length%2==0) { assemble(nums,copy,nums.length-2); assemble(nums,copy,nums.length-1); } else { assemble(nums,copy,nums.length-1); assemble(nums,copy,nums.length-2); } } }
흔들기 정렬을위한 C ++ 코드
class Solution { public: int index=0; public: void assemble(vector<int>& nums,vector<int>& copy,int start) { int i=0; for(i=start;i>-1;i=i-2) { nums[i]=copy[index]; index++; } } public: void wiggleSort(vector<int>& nums) { vector<int>copy(nums); sort(copy.begin(), copy.end()); if(nums.size()%2==0) { assemble(nums,copy,nums.size()-2); assemble(nums,copy,nums.size()-1); } else { assemble(nums,copy,nums.size()-1); assemble(nums,copy,nums.size()-2); } } };
흔들기 정렬을위한 복잡성 분석
위 문제에 대한 시간 복잡성 = O (n log n)
위의 방법으로 Wiggle 정렬을위한 공간 복잡성 = O (n)
어떻게?
- 사용 된 정렬 작업은 시간 복잡도가 O (n logn) 인 내장 병합 정렬입니다.
- 어셈블 함수에 대한 각 호출에서
- 우리는 대체 요소를 살펴보고 그에 따라 사본에서 원래 배열로 배치합니다.
- 따라서 요소가 모두 제자리에 배치 될 때까지 배열의 모든 요소를 살펴 봅니다.
- 배열로 이동하면 시간 복잡도가 O (n)
- 그러나이 경우 정렬 작업은 시간 복잡도를 O (n logn)로 가져 오는 더 많은 비용이 드는 것으로 나타났습니다.
- 요소로 복사 배열을 만들었을 때 공간 복잡성은 O (n), 즉 선형
