The LeetCode algorithm learns — array — to find the minimum value in a rotation-sort array

Today, I would like to share with you the next LeetCode medium difficulty problem [Finding the minimum value in a rotating sort array](leetcode-cn.com/problems/co…).

Here is mainly to share ideas and comments, for you to better understand the problem solution, the code part is to refer to LeetCode translated into javascript code,

The title

Given an array of length n, pre-arranged in ascending order, through 1 to N rotations, the input array. For example, the original array nums = [0,1,2,4,5,6,7] might get: If you rotate it four times, you get [4,5,6,7,0,1,2]. If you rotate it seven times, you get [0,1,2,4,5,6,7]. Array [a [0], a [1], a [2],… and a [n – 1]] array to the result of the rotation a [a] [n – 1, a [0], a [1], a [2],… and a [n – 2]].

You are given an array nums with different element values, which is originally an ascending array and has been rotated several times as described above. Find and return the smallest element in the array

Example 1: Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array is [1,2,3,4,5]. Rotate it three times to get the input array. Example 2: Input: nums = [4,5,6,7,0,1,2] Output: 0 Example 3: Input: NUMs = [11,13,15,17] Output: 11 Explanation: The original array is [11,13,15,17]. Rotate it four times to get the input array.Copy the code

Analysis of the

1. Rotate the array after ascending sort, think of binary search

2. Only if the array is selected, then the minimum value must be on the side that is not in the ascending array.

Unless the array is an ascending sequence from left to right

3. There is no need to redo the element because it does not repeat

There are 2 ways to do this.

1. Binary search, ascending method

2. Binary search, comparing the first element method

Solution 1: binary search, ascending method (using the array ascending characteristics to find the minimum value)

Train of thought1.Return the first element nums[l] if the array is ascending from left to right2.Return nums[l] if nums[l]===nums[r] if nums[l]===nums[r] if nums[l]===nums[r]3.If nums[l]>nums[r] indicates that there is an unordered array in the array, use dichotomy to find */var findMin = function (nums) {
  let l = 0;
  let r = nums.length - 1;

  while (l <= r) {
    Return Nums[l] if Nums[l] = Nums[r]
    if (nums[l] <= nums[r]) {
      return nums[l];
    }

    // If there is an unordered array in the array, narrow it down by binary search
    const mid = Math.floor(l + (r - l) / 2);
    if (nums[l] > nums[mid]) {
      // Note that the smallest index exists in an unordered array, so it must not be r=mid-1, otherwise the answer will be missed
      r = mid;
    } else {
      // If the array is ordered, narrow it down by l=mid+1
      l = mid + 1; }}};/* Complexity time O(logn) space O(1) */
Copy the code

(Image from Leetcode)

Solution two: binary search, contrast with the first element method

Train of thought1.If it's ordered or relative this returns nums[l]2.If there is an unordered array, the left side of the smallest element must be greater than the first element, and the right side must be less than the first element */var findMin = function (nums) {
  let l = 0;
  let r = nums.length - 1;

  if (nums[l] <= nums[r]) {
    return nums[l];
  }

  If nums[0] is smaller than nums[0], it will become a wireless loop */
  while (l < r) {
    // Return l if left to right is ascending
    
    const mid = Math.floor(l + (r - l) / 2);

    if (nums[0] > nums[mid]) {
      // In this case, it must be r=mid or you will miss the answer
      r = mid;
    } else {
      // Narrow the interval to the right
      l = mid + 1; }}return nums[l];
};

/* Complexity time O(logn) space O(1) */

Copy the code

(Photo taken from leetCode)

conclusion

So this problem, again, is looking at your understanding of binary search and rotating arrays, and if you practice and understand a lot, you’ll get the hang of it.

You can look at a column I share (front-end algorithm) there are more questions about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me a like, thank you very much

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Part of the material in this article comes from the network. If there is infringement, please contact delete, [email protected]