zzzrf：微软面试题：寻找旋转排序数组中的最小值
假设一个排好序的数组在其某一未知点发生了旋转（比如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2 ）。你需要找到其中最小的元素。
→在线做题地址
样例 1:
输入：[4, 5, 6, 7, 0, 1, 2]
输出：0
解释：
数组中的最小值为 0
样例 2:
输入：[2,1]
输出：1
解释：
数组中的最小值为 1
解题思路
- 最直接的是暴力解法，搜索整个数组找到最小元素，时间复杂度为 O(n)。
- 我们可以旋转数组的特性，用改进后的二分查找来解决，时间复杂度为 O(logn)。
算法流程
- 使用二分法来寻找最小值，如图所示可以帮助我们理解算法过程。
- 设置双指针 left 和 right 指向数组 nums 两端。
- 第一次分类讨论：比较 nums[left]和 nums[right]
- 如果 nums[left] < nums[right]，说明数组没有旋转过，仍然是升序排列。我们直接 return nums[left]。
- 反之，说明数组非单调，进入到第二次分类讨论。
- 第二次分类讨论：比较 nums[left]和 nums[mid]，其中 mid 是二分中点。
- 如果 nums[left] > nums[mid]，可以证明此时数组右半边是升序的，那我们就不用考虑右半边了。最小值一定在[left, mid]间，令 right = mid 。
- 如果 nums[left] <= nums[mid]，可以证明此时数组左半边是升序的，于是我们不需要考虑左半边。最小值一定在(mid, right]间，令 left = mid + 1 。
- 直到 left == right 时，此时指向的就是最小值，return nums[left]。
等效方法
- 上述算法中，第二次分类讨论我们比较的是 nums[left]和 nums[mid]的大小关系，其实比较 nums[right]和 nums[mid]的大小也是一样的。
- nums[left] > nums[mid]，等效于 nums[mid] < nums[right]
- nums[left] <= nums[mid]，等效于 nums[mid] > nums[right]
- 有兴趣可以证明一下。代码如何实现，看个人的 preference 啦。
复杂度分析
- 时间复杂度: O(log(n))，n 为 nums 的长度。同二分查找的时间复杂度。
- 空间复杂度: $O(1) $。没有使用额外空间。
public class Solution {
/**
* @param nums: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
// 二分法
while (left < right){
// 最小值在 left
if (nums[left] < nums[right]){
return nums[left];
}
int mid = left + (right - left) / 2;
// 最小值在[left, mid]
if (nums[left] > nums[mid]){
right = mid;
}
// 最小值在(mid, right]
else{
left = mid + 1;
}
}
return nums[left];
}
}
更多题解参考
ErwinCheung：真大佬果然清一色的 java
LeetCode题解15.3-sum题目地址 https://leetcode.com/problems/3sum/description/ 题目描述 Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in…
LeetCode题解子数组的最大乘积给定一个长度为N的整数数组，只允许乘法，不能用除法。计算任意 N - 1 个数的组合中乘积最大的一组，并写出算法的时间复杂度。题解：``` .js/** * 动态规划，设dp[i]为以第i个元素结尾的最大乘积， * 它可能是和dp[j..0]（j<i）的最大值或者最小值或者只有它自己构成最大乘积 * * 所以每次需要dp[i]里记录最大值和最小值 * …
LeetCode题解 缺失的第一个正数给定一个未排序的整数数组，找出其中没有出现的最小的正整数。示例 1:输入: [1,2,0]输出: 3示例 2:输入: [3,4,-1,1]输出: 2示例 3:输入: [7,8,9,11,12]输出: 1说明:你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。题解：数组arr长度为len，要找到最小正整数x，x 肯定在[1, len + 1]之间，…
LeetCode题解585. 山脉序列中的最大值描述给 n 个整数的山脉数组，即先增后减的序列，找到山顶（最大值）```样例例1:输入: nums = [1, 2, 4, 8, 6, 3] 输出: 8例2:输入: nums = [10, 9, 8, 7], 输出: 10```扩展：遇到重复元素该怎么办？你有没有发现一个规律 无论查找还是回溯，寻找最优解 都是不停去尝试，关键是如何减少尝试的次数。题目链接：…
LeetCode题解645. 错误的集合集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。示例 1:输入: nums = [1,2,2,4]输出: [2,…