LCR 128.库存管理

库存管理(寻找旋转排序数组最小值)

题目

解题

我的思路

我知道最小值的位置的特点是，该位置的数小于其前一个位置的数，当然这里存在一个特殊点是当这个位置为0时，没有前一个数字。

//没写出来
var findMin = function(nums) {
    // 特点在于，目标数的前一位大于目标数
    //特殊情况是目标数的下表为0，说明旋转了0次
    let left = 0,right = nums.length
    while(left<right){
        let mid = left + Math.floor((right - left)/2)
        if(mid === 0) return nums[mid]
        else{
            if(nums[mid] < nums [mid-1]) return nums[mid]
            else if()
        }

    }
};

正确思路

我们可以认为这个数组是由重复值的。那么一个经过旋转之后的数组可视化后如下图所示。数组中最后一个元素的大小为x，如图中虚线所示。

它具如下的特点：

• 最小值右边的元素均小于等于x
• 最小值左边的元素均大于等于最小值

  基于上述特性才使得本题可以使用二分查找法解决。

二分查找的情况可以分为3类
在二分查找的每一步中，左边界为 low，右边界为 high，区间的中点为 pivot，最小值就在该区间内。我们将中轴元素 nums[pivot]与右边界元素 nums[high]进行比较，可能会有以下的三种情况：

1、nums[pivot] > nums[high],说明最小值在pivot与high之间。low = pivot + 1

2、nums[pivot] < nums[high],说明最小值不在在pivot与high之间。high = pivot - 1

3、nums[pivot] === nums[high],这是由于存在重复值。high=high-1

当二分查找结束时，我们就得到了最小值所在的位置。

var stockManagement = function(stock) {
  let low = 0;
    let high = stock.length - 1;
    while (low < high) {
        const pivot = low + Math.floor((high - low) / 2);
        if (stock[pivot] < stock[high]) {
            high = pivot;
        } else if (stock[pivot] > stock[high]) {
            low = pivot + 1;
        } else {
            high -= 1;
        }
    }
    return stock[low];
};