11. Rotate the smallest number in the array

LeetCode leetcode-cn.com/problems/xu…

The title

Moving the beginning elements of an array to the end of the array is called array rotation. Take a rotation of an incrementally sorted array and print the smallest element of the rotation array. For example, the array [3,4,5,1,2] is a rotation of [1,2,3,4,5], whose minimum value is 1.

Example 1:

Input: [3,4,5, 2] Output: 1Copy the code

Example 2:

Input: [2,2,2,0,1] output: 0Copy the code

15. Attention: leetcode-cn.com/problems/fi…

Their thinking

Binary search

Let’s start by repeating the concept of rotating an array. In this case, rotating an array means placing the first elements of an ascending array at the end of the array.

So, according to this concept, we can find that. After the rotation, the array nums is split into two ascending arrays, which are set to nums1 and nums2, and the elements of the trailing array nums2 are less than or equal to the elements of the preceding array nums1. So now the question is how do I find two arrays rotated in ascending order? Because as long as you find two rotated arrays, the first element in the NUMs2 array is the required answer.

So, in this case, we can consider using binary search to find a cut-off point (the cut-off point is the first element of the trailing ascending array), the array to the left of the cut-off point is nums1, and the array to the right of the cut-off point (including the cut-off point) is nums2.

Nums1 indicates the left ascending array after rotation, nums2 indicates the right ascending array after rotation.

  • First, define a pointerleft,rightRefer tonumsBoth ends of the array, andmidIs the midpoint of every binary search;
  • Start to compare (nums1Is greater than or equal tonums2The elements of the), the following three situations will occur:
    • ifnums[mid] > nums[right], thenmidIt must benums1In this array, the cut-off point is in the interval(mid, right],left=mid+1;
    • ifnums[mid] < nums[right], thenmidIn thenums2Array, where the cut-off point falls on the interval[left, mid],right=mid;
    • ifnums[mid] == nums[right](here because the element is allowed to repeat), there will be a fuzzy boundary situation, first say the conclusion (later analysis), letrightMove the pointer forward and makeright -= 1.

Nums [mid] == nums[right]; nums[mid] == nums[right]; nums[right] = nums[right]

  • When given an array[1, 1, 0, 1]In this case,left = 0, right = 3, mid = 1:
    • nums[mid] == nums[right]In this case, mid is in the left arraynums1In the.
  • When given an array[1, 0, 1, 1, 1]At this time,left = 0, right = 4, mid = 2:
    • nums[mid] == nums[right], but now mid is in the right arraynums2In the.

In this case, it is impossible to determine whether mid falls in nums1 or nums2. In the previous conclusion, right -= 1 is given to solve this problem. Based on the possible situations analyzed above, the feasibility of this conclusion is analyzed now:

  • whenmidFall in thenums1Array, becausenums1Is greater than or equal to any element ofnums2, that is (let the cut-off point bepoint)nums[point] <= nums[mid] == nums[right], then:
    • ifnums[point] < nums[right], hererightThe element on the left has a small value, let’sright -= 1Later,pointOr in the[left, right]In this interval;
    • ifnums[point] == nums[right], pay attention to the cut-off index herepoint 与 rightStudent: Equal case. At this time, makeright-=1At this time,pointWill not[left, right]In this interval. Suppose I have the following array[1, 1, 2, 1)Here,left = 0, right = 3, mid = 1We can see that the cut-off point is that last 1. At this timepoint == rightIf, forright -= 1So here’s the last one1Will be discarded. But the result will still come back1Because abandoning the last1After continuing binary search, the cut-off point must fall at[left, mid], and the values of the elements in this interval are equal tonums[point]. So it returns the correct value.
  • whenmidFall in thenums2In the array, that is to say[mid, right]All the elements in this interval are equal. At this point to makeright -= 1I’m just dropping a duplicate value, andpointOr fall in[left, right]In this interval.

The following is a diagram of the algorithm implementation:

The specific implementation code is as follows.

Code implementation

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        left = 0
        right = len(numbers) - 1

        while left < right:
            # take midpoint
            mid = left + (right - left) // 2
            Numbers [mid] > numbers[right]
            if numbers[mid] > numbers[right]:
                left = mid + 1
            # numbers[mid] < numbers[right]
            elif numbers[mid] < numbers[right]:
                right = mid
            # number [mid] == right-=1 # number [mid] == right-=1
            else:
                right -= 1

        return numbers[left]
Copy the code

Achieve results

Welcome to attention

Public Account [Collection of Books]