制作一个排序过的数组,数组在某个你事先不知道的枢轴上旋转 也就是说,0 1 2 4 5 6 7可能变成4 5 6 7 0 1 2 求最小元素,Java,输出随机数组,排序数组,最小元素
时间: 2024-09-10 22:28:28 浏览: 41
Python算法题源代码-LeetCode(力扣)-搜索旋转排序数组
在Java中,处理旋转排序数组(例如,`[4, 5, 6, 7, 0, 1, 2]`)并找到最小元素可以采用二分查找的方法。这是因为虽然数组看起来像是随机分布的,但是我们知道它一定是在某一点(枢轴)之后开始旋转的,所以旋转部分还是有序的。
首先,我们可以假设第一个元素是最小值,然后从第二个元素开始进行比较。如果当前元素小于已知的最小值,则枢轴不可能在其右侧,因为右侧是递增的。所以我们每次都将搜索范围缩小一半,直到找到最小元素或者确定整个剩余部分都是大于当前最小值的。
以下是简单的Java代码实现:
```java
import java.util.Arrays;
import java.util.Random;
public class RotateArray {
public static int findMin(int[] nums) {
if (nums == null || nums.length <= 1) {
return Arrays.stream(nums).min().getAsInt();
}
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// 如果中间元素大于左边界,说明最小值在左半边
if (mid > 0 && nums[mid] >= nums[left]) {
right = mid - 1;
} else { // 否则,最小值在右半边或就是左边界
left = mid + 1;
}
}
return nums[left];
}
public static void main(String[] args) {
Random rand = new Random();
int[] nums = new int[10]; // 或者你想要的任意长度
for (int i = 0; i < nums.length; i++) {
nums[i] = rand.nextInt(100); // 生成随机整数填充数组
}
Arrays.sort(nums); // 先对数组进行排序
System.out.println("原始数组: " + Arrays.toString(nums));
int minElement = findMin(nums);
System.out.println("最小元素: " + minElement);
}
}
```
在这个例子中,`findMin`方法会返回旋转数组中的最小元素。注意这个解决方案假定了输入数组至少包含两个元素,并且不会改变原数组。
阅读全文