旋转排序数组中的最小值

Question

我正在看这个leetcode挑战：

假设按升序排序的数组在某个枢轴处旋转 你事先不知道。

（即

[0,1,2,4,5,6,7]

可能会变成

[4,5,6,7,0,1,2]

）。

找到最小元素。

您可以假设数组中不存在重复项。

我在repl.it上找到了这个解决方案：

function findMin(nums) {
    if (nums.length === 1) { //Edge
        return nums[0];
    }

    let left = 0, right = nums.length - 1 //Two pointers 

    if (nums[right] > nums[0]) { //Sorted array case
        return nums[0];
    }

    while (left < right) { //Shifted unsorted array 
        const mid = Math.floor((left + right) / 2); 
        if (nums[mid] > nums[right]) left = mid + 1; //If midpoint is larger than last element, look right
        else right = mid; //Else look left 
  }
  return nums[left];
}

我的问题与以下行背后的逻辑有关：

if (nums[mid] > nums[right]) left = mid + 1; 我一直在尝试在纸上写出示例，但是有人可以解释为什么上面的行是正确的逻辑吗？是因为移位数组中所有最小的元素总是位于数组的右侧吗？

Answer 1

您已经使用以下方法检查了非移位排序数组：

if (nums[right] > nums[0]) {                            
    //Sorted array case
        return nums[0];
    }

现在我们举个例子：

3 4 5 2 1

代码：

while (left < right) { //Shifted unsorted array 
        const mid = Math.floor((left + right) / 2); 
        
        if (nums[mid] > nums[right]) left = mid + 1; 
        //If midpoint is larger than last element, look right
        
        else right = mid; //Else look left 
  }

迭代 1： 左 = 0 ，右 = 4 -> 中 = 2

现在左侧应该是 mid + 1，因为较低的值在右侧。当您发言时，这不会导致索引错误。

迭代 2： 左 = 3，右 = 4 -> 中 = 3

现在右边变成了中间，如 nums[mid]

<= nums[right].

因此，返回 nums[left] = nums[3] = 1

Answer 2

如果您可视化旋转的数组，例如 [6,7,8,9,1,2,3,4,5]，您将得到以下模式：

            9
         8
      7
   6
                            5
                         4
                      3
                   2
                1

   left         k           right

1 是要查找的最小值，它位于索引

k 处。一旦你有了索引mid

，就有两种可能性：

• mid >= k

  ：我们可以看到，在这种情况下，只有这样，

  a[mid] <= a[right]
• mid < k

  ：我们可以看到，在这种情况下，只有这样，

  a[mid] > a[right]

在第一种情况下，

mid

右侧的所有元素都可以被忽略，因此我们设置

right = mid

（最小值仍然可以是

atmid

）。

在第二种情况下，

mid

左侧的所有元素都可以被忽略，包括

mid

本身，因此我们可以设置

left = mid + 1

。

每次调整

left

或

right

时，

k

都会保持在

left

和

right

之间的缩小范围内，因此我们以相同的逻辑重复相同的模式。

Answer 3

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int low = 0, high = n - 1;
        int ans = Integer.MAX_VALUE;

        while (low <= high) {
            int mid = low + (high - low) / 2; // Avoid potential overflow
            
            // If the array is already sorted or has only one element
            if (nums[low] <= nums[high]) {
                ans = Math.min(ans, nums[low]);
                break;
            }

            // Check if the left part is sorted
            if (nums[low] <= nums[mid]) {
                ans = Math.min(ans, nums[low]);
                low = mid + 1;
            } else {
                // Right part is sorted or the pivot point is in this section
                ans = Math.min(ans, nums[mid]);
                high = mid - 1;
            }
        }
        return ans;
    }
}