This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

I. Title Description:

Find the minimum value in the rotation sort array

Given an array of length N, sorted in ascending order, rotated 1 to n times, the input array is obtained. For example, the original array nums = [0,1,2,4,5,6,7] might be changed to: If you rotate it four times, you get [4,5,6,7,0,1,2] and 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. It was originally an array sorted in ascending order and rotated several times as described above. Find and return the smallest element in the array.

Example 1:

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

Example 2:

Input: nums = [4,5,6,7,0,1,2] Output: 0 Description: The original array is [0,1,2,4,5,6,7], rotated four times to get the input array.Copy the code

Example 3:

Input: nums = [11,13,15,17] Output: 11 Description: The original array is [11,13,15,17], rotated four times to get the input array.Copy the code

Tip:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All integers in NUMs are different
  • Nums was originally an ascending sorted array, rotated 1 to n times

Ii. Analysis of Ideas:

  1. Find the minimum value after traversing

AC code

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let min = nums[0];
    for(let i = 1; i < nums.length; i ++) {
        if(nums[i] < min) min = nums[i];
    }
    return min;
};
Copy the code

The execution result

Results: Beat 18.55% user memory consumption of 38.1 MB in all JavaScript commits, beat 38.99% user memory consumption of all JavaScript commits, with execution time: 96 msCopy the code

Disadvantages: Maximum time complexity

  1. Take the first one after the array is resorted in ascending order

AC code

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    nums.sort((a, b) => {
        return a - b;
    });
    return nums[0];
};
Copy the code

The execution result

Results: Beat 97.16% of users memory consumption of 39.1 MB in all JavaScript commits and beat 5.05% of users in all JavaScript commits with execution time: 72 msCopy the code

Disadvantages: Longest time complexity

  1. dichotomy
  • Find an ordered array, try usingdichotomy
  • use(end - start) / 2Get the middle positionmid, the use ofMath.floorTake down the whole
  • Judge the middle position valuenums[mid]And the trailing position valuenums[end]Is it in ascending order? If it is in ascending order, the minimum value is in the left part of the middle position, and the end position is in the original middle positionend = mid
  • If it is not in ascending order, the minimum value is on the right part. Set the starting position to the original middle position plus onestart = mid + 1
  • Continue the dichotomy until the start position is no less than the end position, returning the value of the start positionnums[start]

AC code

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let start = 0;
    let end = nums.length - 1;
    while (start < end) {
        const mid = start + Math.floor((end - start) / 2);
        if (nums[mid] < nums[end]) {
            end = mid;
        } else {
            start = mid + 1;
        }
    }
    return nums[start];
};
Copy the code

The execution result

Results: Beat 64.33% of all JavaScript commits with memory consumption of 37.7 MB and 94.00% of all JavaScript commits with execution time: 84 msCopy the code

Iii. Summary:

  • Array traversal lookup is the least efficient
  • Using the array with its own sort can use JavaScript internal optimization, improve part of the efficiency
  • Binary search improves search efficiency