LeetCode - 회전 정렬 배열에서 검색 II

문제 설명

감소하지 않는 순서로 정렬된 정수 배열 nums가 있습니다(반드시 고유한 값이 있는 것은 아님).

함수에 전달되기 전에 nums는 결과 배열이 [nums[k], nums[k + 1], ..., nums가 되도록 알 수 없는 피벗 인덱스 k(0 <= k < nums.length)에서 회전합니다. [n - 1], nums[0], nums[1], ..., nums[k - 1]] (인덱스 0). 예를 들어 [0, 1, 2, 4, 4, 4, 5, 6, 6, 7]은 피벗 인덱스 5에서 회전하여 [4, 5, 6, 6, 7, 0, 1, 2, 4, 4].

회전 후 배열 숫자와 정수 대상이 주어지면 대상이 숫자이면 true를 반환하고 숫자가 아니면 false를 반환합니다.

전체 작업 단계를 최대한 줄여야 합니다.

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

예 1:

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 0
Output: true

예 2:

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3
Output: false

제약:

- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5

설명

이 문제에 대한 해결책은 이전 [Search in Rotated Sorted Array(https://alkeshghorpade.me/post/leetcode-search-in-rotated sorted-array)]와 유사합니다. 유일한 차이점은 중복이 있기 때문에 nums[low] == nums[mid]가 가능성이 있으며 이 경우를 별도로 처리해야 한다는 것입니다.

알고리즘으로 직접 이동해 보겠습니다.

// search function
- if low > high
    - return -1

- set mid = low + (high - low) / 2

- if nums[mid] == key
    - return true

- if nums[low] == nums[mid + 1] && nums[high] == nums[mid]
    - low++
    - high--
    - search(nums, low, high, key)

if nums[low] <= nums[mid]
    - if key >= nums[low] && key <= nums[mid]
        - return search(nums, low, mid - 1, key)

    - return search(nums, mid + 1, high, key)

if key >= nums[mid] && key <= nums[high]
    - return search(nums, mid + 1, high, key)

- return search(nums, low, mid - 1, key)

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

C++ 솔루션

class Solution {
public:
    bool searchUtil(vector<int>& nums, int low, int high, int target) {
        if(low > high) {
            return false;
        }

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

        if(nums[mid] == target){
            return true;
        }

        if(nums[low] == nums[mid] && nums[high] == nums[mid]){
            low++;
            high--;
            return searchUtil(nums, low, high, target);
        }

        if(nums[low] <= nums[mid]){
            if(target >= nums[low] && target <= nums[mid]){
                return searchUtil(nums, low, mid - 1, target);
            }

            return searchUtil(nums, mid + 1, high, target);
        }

        if(target >= nums[mid] && target <= nums[high]){
            return searchUtil(nums, mid + 1, high, target);
        }

        return searchUtil(nums, low, mid - 1, target);
    }

    bool search(vector<int>& nums, int target) {
        bool result = searchUtil(nums, 0, nums.size() - 1, target);
        return result;
    }
};

골랑 솔루션

func searchUtil(nums []int, low, high, target int) bool {
    if low > high {
        return false
    }

    mid := low + (high - low) / 2

    if nums[mid] == target {
        return true
    }

    if nums[low] == nums[mid] && nums[high] == nums[mid] {
        low++
        high--
        return searchUtil(nums, low, high, target)
    }

    if nums[low] <= nums[mid] {
        if target >= nums[low] && target <= nums[mid] {
            return searchUtil(nums, low, mid - 1, target)
        }

        return searchUtil(nums, mid + 1, high, target)
    }

    if target >= nums[mid] && target <= nums[high] {
        return searchUtil(nums, mid + 1, high, target);
    }

    return searchUtil(nums, low, mid - 1, target);
}

func search(nums []int, target int) bool {
    return searchUtil(nums, 0, len(nums) - 1, target)
}

자바스크립트 솔루션

var searchUtil = function(nums, low, high, target) {
    if(low > high) {
        return false;
    }

    let mid = low + (high - low)/2;

    if(nums[mid] == target){
        return true;
    }

    if(nums[low] == nums[mid] && nums[high] == nums[mid]){
        low++;
        high--;
        return searchUtil(nums, low, high, target);
    }

    if(nums[low] <= nums[mid]){
        if(target >= nums[low] && target <= nums[mid]){
            return searchUtil(nums, low, mid - 1, target);
        }

        return searchUtil(nums, mid + 1, high, target);
    }

    if(target >= nums[mid] && target <= nums[high]){
        return searchUtil(nums, mid + 1, high, target);
    }

    return searchUtil(nums, low, mid - 1, target);
};

var search = function(nums, target) {
    return searchUtil(nums, 0, nums.length - 1, target);
};

문제를 연습해 봅시다.

Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3

// search function
Step 1: searchUtil(nums, 0, nums.size() - 1, target)
        searchUtil(nums, 0, 6, 0)

// searchUtil function
Step 2: low > high
        0 > 6
        false

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

Step 4: if nums[mid] == target
           nums[3] == 3
           0 == 3
           false

Step 5: if nums[low] == nums[mid] && nums[high] == nums[mid]
           nums[0] == nums[3] && nums[6] == nums[3]
           2 == 0 && 2 == 0
           false

Step 6: if nums[low] <= nums[mid]
           nums[0] <= nums[3]
           2 <= 0
           false

Step 7: if target >= nums[mid] && target <= nums[high]
           3 >= nums[3] && 3 <= nums[6]
           3 >= 0 && 3 <= 2
           false

Step 8: searchUtil(nums, low, mid - 1, target)
        searchUtil(nums, 0, 2, 3)

// searchUtil function
Step 9: low > high
        0 > 2
        false

Step 10: mid = low + (high - low)/2
             = 0 + (2 - 0)/2
             = 0 + 2/2
             = 1

Step 11: if nums[mid] == target
            nums[1] == 3
            5 == 3
            false

Step 12: if nums[low] == nums[mid] && nums[high] == nums[mid]
            nums[0] == nums[1] && nums[2] == nums[1]
            2 == 5 && 6 == 5
            false

Step 13: if nums[low] <= nums[mid]
            nums[0] <= nums[1]
            2 <= 5
            true

            if target >= nums[low] && target <= nums[mid]
               3 >= nums[0] && 3 <= nums[1]
               3 >= 2 && 3 <= 5
               true

               return searchUtil(nums, low, mid - 1, target)
                      searchUtil(nums, 0, 1 - 1, 3)
                      searchUtil(nums, 0, 0, 3)

// searchUtil function
Step 14: if low > high
            0 > 0
            false

Step 15: mid = low + (high - low)/2
             = 0 + (0 - 0)/2
             = 0 + 0/2
             = 0

Step 16: if nums[mid] == target
            nums[0] == 3
            2 == 3
            false

Step 17: if nums[low] == nums[mid] && nums[high] == nums[mid]
            nums[0] == nums[0] && nums[0] == nums[0]
            2 == 2 && 2 == 2
            true

            low++
            low = 1

            high--
            high = -1

            return searchUtil(nums, low, high, target)
                   searchUtil(nums, 1, -1, 3)

// searchUtil function
Step 14: if low > high
            1 > -1
            true

            return false

// We go back from Step 14 to Step 9 to Step 2 to Step 1 because of recursion

We return the answer as false.