LeetCode - 회전 정렬 배열에서 최소값 찾기

문제 설명

오름차순으로 정렬된 길이 n의 배열이 1에서 n번 사이에서 회전한다고 가정합니다.
예를 들어 배열 nums = [0, 1, 2, 4, 5, 6, 7]은 다음과 같을 수 있습니다.

[4, 5, 6, 7, 0, 1, 2] 4번 회전한 경우.
[0, 1, 2, 4, 5, 6, 7] 7번 회전한 경우.
배열 [a[0], a[1], a[2], ..., a[n-1]]을 1번 회전하면 결과가 나타납니다.
배열 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]에서.

고유 요소의 정렬된 회전 배열 숫자가 주어지면 이 배열의 최소 요소를 반환합니다.

O(log n) 시간에 실행되는 알고리즘을 작성해야 합니다.

다음에서 가져온 문제 설명: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ .

예 1:

Input: nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: The original array was [1, 2, 3, 4, 5] rotated 3 times.

예 2:

Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: The original array was [0, 1, 2, 4, 5, 6, 7] and it was rotated 4 times.

예 3:

Input: nums = [11, 13, 15, 17]
Output: 11
Explanation: The original array was [11, 13, 15, 17] and it was rotated 4 times.

제약:

- n == nums.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- All the integers of nums are unique
- nums is sorted and rotated between 1 and n times

설명

무차별 대입 방식

순진한 접근 방식은 O(N) 시간이 걸리는 선형 검색을 수행하는 것입니다. (i - 1) 번째 인덱스 다음에 더 작은 숫자가 나타나는 i 번째 인덱스를 찾아야 합니다.

이진 검색

배열이 회전하지만 정렬되기 때문에 이진 검색 구현을 수정할 수 있습니다. 회전된 배열에는 정렬된 두 개의 세그먼트가 있습니다. 정렬이 방해받는 인덱스는 배열의 가장 작은 요소에서 발생합니다.

알고리즘을 확인해 봅시다:

- set low = 0
      high = nums.size() - 1

- loop while low < high
  - set mid = low + (high - low) / 2

  - if nums[low] <= nums[mid] && nums[high] >= nums[mid]
    - set high = mid - 1
  - else if nums[low] <= nums[mid] && nums[high] <= nums[mid]
    - set low = mid + 1
  - else if nums[mid] <= nums[low]
    - set high = mid

- return nums[low]

C++, Golang 및 Javascript의 솔루션을 확인해 봅시다.

C++ 솔루션

class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0;
        int high = nums.size() - 1;

        while(low < high) {
            int mid = low + (high - low) / 2;

            if(nums[low] <= nums[mid] && nums[high] >= nums[mid])
                high = mid - 1;
            else if(nums[low] <= nums[mid] && nums[high] <= nums[mid])
                low = mid + 1;
            else if(nums[mid] <= nums[low])
                high = mid;
        }

        return nums[low];
    }
};

골랑 솔루션

func findMin(nums []int) int {
    low, mid := 0, 0
    high := len(nums) - 1

    for low < high {
        mid = low + (high - low) / 2

        if nums[low] <= nums[mid] && nums[high] >= nums[mid] {
            high = mid - 1
        } else if nums[low] <= nums[mid] && nums[high] <= nums[mid] {
            low = mid + 1
        } else if nums[mid] <= nums[low] {
            high = mid
        }
    }

    return nums[low];
}

자바스크립트 솔루션

var findMin = function(nums) {
    let low = 0;
    let high = nums.length - 1;

    while(low < high) {
        let mid = low + Math.floor((high - low) / 2);

        if(nums[low] <= nums[mid] && nums[high] >= nums[mid])
            high = mid - 1;
        else if(nums[low] <= nums[mid] && nums[high] <= nums[mid])
            low = mid + 1;
        else if(nums[mid] <= nums[low])
            high = mid;
    }

    return nums[low];
};

알고리즘을 시험 실행해 봅시다.

Input: nums = [4, 5, 6, 7, 0, 1, 2]

Step 1: low = 0
        high = nums.size() - 1
             = 7 - 1
             = 6

Step 2: loop while low < high
          0 < 6
          true

          mid = low + (high - low) / 2
              = 0 + (6 - 0) / 2
              = 3

          if nums[low] <= nums[mid] && nums[high] >= nums[mid]
             nums[0] <= nums[3] && nums[6] >= nums[3]
             4 <= 7 && 2 >= 7
             false

          else if nums[low] <= nums[mid] && nums[high] >= nums[mid]
                  nums[0] <= nums[3] && nums[6] <= nums[3]
                  4 <= 7 && 2 <= 7
                  true

                  low = mid + 1
                      = 3 + 1
                      = 4

Step 3: loop while low < high
          4 < 6
          true

          mid = low + (high - low) / 2
              = 4 + (6 - 4) / 2
              = 4 + 1
              = 5

          if nums[low] <= nums[mid] && nums[high] >= nums[mid]
             nums[4] <= nums[5] && nums[6] >= nums[5]
             0 <= 1 && 2 >= 1
             true

             high = mid - 1
                  = 5 - 1
                  = 4

Step 4: loop while low < high
          4 < 4
          false

Step 5: return nums[low]
               nums[4]
               0

We return the answer as 0.