制作一个排序过的数组,数组的个数n由用户决定,数组在某个你事先不知道的枢轴上旋转(随机根据某个元素旋转) 也就是说,0 1 2 4 5 6 7可能变成4 5 6 7 0 1 2 求最小元素,Java,输出排序数组,旋转后的数组,最小元素
时间: 2024-09-10 09:29:28 浏览: 62
在Java中,你可以使用二分查找算法来寻找旋转排序数组的最小元素。首先,我们需要确定数组是否已经旋转以及旋转的位置。这里是一个简单的步骤:
1. **判断基准元素**:
- 比较数组的第一个元素和中间元素,如果第一个大于中间,说明数组可能右旋了;如果小于,则左旋。
2. **缩小搜索范围**:
- 如果已知左旋,从第一个元素开始找最左边的大于中间元素的值,这是新的"枢轴";
- 如果已知右旋,从最后一个元素开始找最小的值,这也是新的"枢轴"。
3. **找到最小元素**:
- 一旦找到新枢轴,最小元素就是枢轴左侧的第一个元素。
以下是Java代码实现:
```java
public class Solution {
public int findMin(int[] nums) {
if (nums.length == 0) return 0;
// 验证数组是否旋转
int left = 0, right = nums.length - 1;
if (nums[left] > nums[right]) {
// 左旋转
while (left < right && nums[left] >= nums[(left + right) / 2]) {
right--;
}
return nums[left];
} else {
// 右旋转
while (left < right && nums[right] <= nums[(left + right) / 2]) {
left++;
}
return nums[left];
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int n = 7; // 用户输入的数组长度
int[] rotatedArray = {4, 5, 6, 7, 0, 1, 2}; // 示例旋转数组
System.out.println("Sorted array: " + Arrays.toString(Arrays.copyOf(rotatedArray, n)));
int minElement = solution.findMin(rotatedArray);
System.out.println("Minimum element: " + minElement);
}
}
```
阅读全文