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 II in the rotation sorted 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,4,4,5,6,7] might be changed to: If you rotate it four times, you get [4,5,6,7,0,1,4] and if you rotate it seven times, you get [0,1,4,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 that may have duplicate element values. It was originally an array in ascending order, rotated several times as described above. Find and return the smallest element in the array.

Example 1:

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

Example 2:

Input: nums = [2,2,2,0,1Copy the code

Tip:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • numsIt was an ascending sort array and carried out1 至 nA rotating

Advanced:

  • This problem is an extension of finding the minimum in a rotated sorted array.
  • Does allowing repetition affect the time complexity of the algorithm? How and why?

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 21.48% of users in all JavaScript commits with execution time: 96 ms memory consumption: 39.1 MB and beat 22.46% of users in all JavaScript commitsCopy 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 55.08% of users in all JavaScript commits with execution time: 88 ms memory consumption: 38.9 MB and beat 66.60% of users in all JavaScript commitsCopy 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, because there are repeated elements, then judge whether the value of the middle position is greater than the value of the end position. If it is, the minimum value is in the right part, and set the starting position to the original middle position plus onestart = mid + 1
  • Otherwise, the trailing position value moves one bit to the left
  • 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;
    let min = nums[0];
    while(start < end) {
        let mid = start + Math.floor((end - start) / 2);
        if(nums[mid] < nums[end]) {
            end = mid;
        } else if(nums[mid] > nums[end]) {
            start = mid + 1;
        } else {
            end --;
        }
    }
    return nums[start];
};
Copy the code

The execution result

Execution result: By displaying details Execution time: 84 ms, beat 73.83% of users in all JavaScript commits Memory consumption: 39 MB, beat 57.42% of users in all JavaScript commitsCopy 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