다음 순열 Leetcode 솔루션

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance 문틀 Facebook 구글 Microsoft 신탁 알레그로 섹션 동네 짱
배열 골드만 삭스 품질 Tik의 톡 두 포인터조회수 49

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

문제 정책

또한 다음 순열 LeetCode 솔루션 – "다음 순열"은 처음 n개의 자연수의 순열인 정수 배열이 주어졌음을 나타냅니다. 우리는 다음을 찾아야 한다 사전순으로 가장 작은 순열 주어진 배열의 교체는 제자리에 있어야 하며 일정한 추가 공간만 사용해야 합니다.

사전순으로 가장 작은 순열이 주어진 입력 배열에 대해 존재하지 않으면 오름차순으로 정렬된 배열을 반환합니다.

예:

Input:  nums = [1,2,3]
Output: [1,3,2]

설명 :

  • 다음 순열은 [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]입니다.
  • [1, 3, 2]는 [1, 2, 3]의 사전순으로 가장 작은 다음 순열입니다.
Input:  nums = [3,2,1]
Output: [1,2,3]

설명 :

  • 입력 배열의 사전순으로 다음으로 가장 작은 순열이 존재하지 않으므로 [1, 2, 3]을 답으로 반환합니다.

접근

아이디어 :

  1. 이 문제를 해결하기 위한 주요 아이디어는 포인터.
  2. 무차별 대입 솔루션은 정렬된 입력 배열의 모든 순열을 생성하는 것입니다. 생성된 모든 순열에 대해 이 순열이 입력 배열의 사전식에서 가장 작은 다음 순열인지 여부를 확인합니다. Brute Force Solution은 시간 복잡도가 증가하기 때문에 시간 제한 초과 판정을 받게 됩니다. n! 여기서 n은 입력 배열의 크기입니다.
  3. 배열의 끝에서 첫 번째 인덱스를 찾습니다. i 그렇게 아리[나] < 아[나+1].
  4. 그런 다음, 찾아 가장 큰 인덱스 j그런 아리[j] > 아[나] 제 > 나는.
  5. 교환 arr[i] 및 arr[j]세그먼트 반전 [i+1,n-1].
  6. 위의 단계에서 형성된 결과 배열은 사전순으로 입력 배열의 가장 작은 다음 순열입니다.

암호

다음 순열 Leetcode C++ 솔루션:

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int index = -1,n = nums.size();
        for(int i=n-2;i>=0;i--){
            if(nums[i]<nums[i+1]){
                index = i;
                break;
            }
        }
        for(int i=n-1;i>index and index!=-1;i--){
            if(nums[i]>nums[index]){
                swap(nums[i],nums[index]);
                break;
            }
        }
        reverse(nums.begin()+index+1,nums.end());
    }
};

다음 순열 Leetcode Java 솔루션:

class Solution {
    public void nextPermutation(int[] nums) {
        int index = -1,n = nums.length;
        for(int i=n-2;i>=0;i--){
            if(nums[i]<nums[i+1]){
                index = i;
                break;
            }
        }
        for(int i=n-1;i>=0 && index!=-1;i--){
            if(nums[i]>nums[index]){
                int temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                break;
            }
        }
        int l = index + 1,r = n - 1;
        while(l<r){
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++;r--;
        }
    }
}

다음 순열 Leetcode 솔루션에 대한 복잡성 분석

시간 복잡성

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

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (1) 우리가 사용하고 있기 때문에 일정한 추가 공간.

참조 : https://docs.microsoft.com/en-us/cpp/standard-library/algorithm-functions?view=msvc-170

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