寻找旋转排序数组中的最小值

题目要求

给定一个长度为 n 的数组 nums，该数组原本是升序排列的，但后来经过了若干次（1 到 n 次）的旋转操作。旋转操作定义为将数组的最后一个元素移动到数组的第一个位置，其余元素依次后移。现在需要你找出并返回旋转后数组中的最小元素。

要求你设计一个算法，其时间复杂度为 O(log n)，以找到这个最小元素。

解题思路

由于原数组是升序的，且旋转操作保持了数组中元素的相对顺序，我们可以利用二分查找的方法来找到最小元素，以满足时间复杂度为 O(log n) 的要求。

初始化指针：设置两个指针 left 和 right，分别指向数组的起始位置和结束位置。
二分查找：当 left 小于 right 时，执行以下操作：
- 找到中间位置 mid = (left + right) / 2。
- 比较 mid 位置的元素和 right 位置的元素：
  - 如果 nums[mid] < nums[right]，则说明最小元素位于 left 和 mid 之间（包括 mid），因此将 right 移动到 mid。
  - 如果 nums[mid] > nums[right]，则说明最小元素位于 mid + 1 和 right 之间，因此将 left 移动到 mid + 1。
循环结束条件：当 left 等于 right 时，循环结束，此时 left 和 right 指向的位置就是最小元素的位置。
返回结果：返回 nums[left] 或 nums[right]，此时它们指向同一个位置，即最小元素的位置。

通过上述步骤，我们可以在 O(log n) 的时间复杂度内找到旋转后数组中的最小元素。

Golang 版本

package main

import "fmt"

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] < nums[right] {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return nums[left]
}

func main() {
    nums := []int{4, 5, 6, 7, 0, 1, 2}
    fmt.Println("The minimum element is:", findMin(nums))
}

这段代码实现了上述的二分查找算法，用于在一个旋转过的升序数组中找到最小的元素。在 main 函数中，我们定义了一个示例数组 nums，并调用 findMin 函数来找到并打印出最小元素。

C++版本

#include <iostream>
#include <vector>

int findMin(std::vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[right]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return nums[left];
}

int main() {
    std::vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    std::cout << "The minimum element is: " << findMin(nums) << std::endl;
    return 0;
}

这段 C++代码实现了一个函数 findMin，它接受一个整数类型的向量 nums 作为参数，并返回旋转后数组中的最小元素。在 main 函数中，我们创建了一个示例向量 nums，并调用 findMin 函数来找到并输出最小元素。

Python 版本

def find_min(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < nums[right]:
            right = mid
        else:
            left = mid + 1
    return nums[left]

# 示例
nums = [4, 5, 6, 7, 0, 1, 2]
print("The minimum element is:", find_min(nums))

这段 Python 代码实现了一个函数 find_min，它接受一个列表 nums 作为参数，并返回旋转后数组中的最小元素。在示例中，我们定义了一个列表 nums 并调用 find_min 函数来找到并打印出最小元素。

Java 版本

public class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        System.out.println("The minimum element is: " + solution.findMin(nums));
    }
}

这段 Java 代码定义了一个 Solution 类，其中包含一个 findMin 方法，用于找到旋转后数组中的最小元素。main 方法中创建了一个示例数组 nums，并调用 findMin 方法来输出最小元素。

Rust 版本

fn find_min(nums: Vec<i32>) -> i32 {
    let (mut left, mut right) = (0, nums.len() - 1);
    while left < right {
        let mid = left + (right - left) / 2;
        if nums[mid] < nums[right] {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    nums[left]
}

fn main() {
    let nums = vec![4, 5, 6, 7, 0, 1, 2];
    println!("The minimum element is: {}", find_min(nums));
}

这段 Rust 代码定义了一个函数 find_min，它接受一个 Vec<i32> 类型的向量 nums 作为参数，并返回旋转后数组中的最小元素。在 main 函数中，我们创建了一个示例向量 nums，并调用 find_min 函数来找到并打印出最小元素。

总结

上述问题的解法基于二分查找算法，适用于在部分有序的数组中查找最小元素。由于数组原本是升序排列的，但经过若干次旋转，数组被分为两个升序的子数组。最小元素是这两个子数组的分界点。

解法的关键步骤如下：

初始化两个指针 left 和 right，分别指向数组的起始位置和结束位置。
进行循环，直到 left 指针小于 right 指针：
- 计算中间位置 mid。
- 判断 mid 位置的元素与 right 位置的元素的大小关系：
  - 如果 nums[mid] 小于 nums[right]，则说明最小元素位于左侧，将 right 指针移动到 mid 位置。
  - 否则，最小元素位于右侧，将 left 指针移动到 mid + 1 位置。
当 left 和 right 指针相遇时，left 指向的位置即为最小元素所在的位置。

这种方法的时间复杂度为 O(log n)，因为每次迭代都会将搜索范围减半，这符合二分查找的性质。无论是在 Python、Java 还是 Rust 语言中，核心算法思想是一致的，只是在语法和一些细节上有所不同。

hot-100