力扣153. 寻找旋转排序数组中的最小值
本文共 914 字，大约阅读时间需要 3 分钟。
为了找到旋转后的数组中的最小元素，我们可以通过以下步骤来解决问题：
方法思路
问题分析：给定一个原本升序排列的数组，经历了若干次旋转。每次旋转会将数组的最后一个元素移动到数组的前面。我们的任务是找到旋转后的数组中的最小元素。 关键观察：旋转后的数组实际上是一个循环左移的结果。最小元素的位置取决于旋转的次数。通过找到数组中第一个位置i，使得nums[i] > nums[i+1]（考虑数组循环性），我们可以确定旋转次数k=i+1。 算法选择：遍历数组，找到满足条件的位置i，然后计算k=i+1。由于数组是循环的，k的值可能会超过数组长度，因此我们需要对k取模运算，得到最终的最小元素位置。 复杂度分析：该方法的时间复杂度为O(n)，因为我们只需遍历数组一次。 解决代码
通过遍历数组，找到第一个位置i，使得nums[i] > nums[(i+1) % n]，然后确定最小元素的位置为k = i + 1。由于数组是循环的，我们对k取模运算，得到最终的最小元素位置。 代码实现：
```html int findMin(int* nums, int n) { int k = 0; for (int i = 0; i < n; i++) { int j = (i + 1) % n; if (nums[i] > nums[j]) { k = i + 1; break; } } return nums[k % n];}
代码解释
初始化变量：k 初始化为0，用于记录最小元素的位置。 遍历数组：从数组开头开始遍历每个元素i。 检查条件：对于每个i，计算下一个位置j = (i + 1) % n。如果nums[i] > nums[j]，则记录k = i + 1，并跳出循环。 取模运算：由于k可能大于数组长度n，使用取模运算确保k是有效的数组索引。 返回结果：返回nums[k % n]，即旋转后的数组中的最小元素。 通过这种方法，我们可以高效地找到旋转后的数组中的最小元素。
转载地址：http://zertz.baihongyu.com/