编写java代码实现:分治算法,1.选第二大 2.选第k小
时间: 2024-09-21 09:05:59 浏览: 47
编写Java代码实现分治算法通常用于解决排序和查找问题,这里我们分别给出两个例子,一个是使用分治法找出数组中的第二大的元素(也称为"最小的最大数"),另一个是找到第k小的元素。
**1. 寻找数组中的第二大的元素 (分治法)**
```java
public class SecondLargest {
public static int findSecondLargest(int[] nums) {
if (nums.length < 2) return Integer.MIN_VALUE; // 如果数组长度小于2,返回最小值
// 分治策略:递归地将数组分为两部分,然后找出每个部分的最大值和第二大的值
int leftMax = findSecondLargest(Arrays.copyOfRange(nums, 0, nums.length / 2));
int rightMax = findSecondLargest(Arrays.copyOfRange(nums, nums.length / 2, nums.length));
// 通过比较左右两部分的最大值和当前部分最大值确定第二大值
int secondLargest;
if (leftMax > rightMax) {
secondLargest = Math.max(leftMax, nums[nums.length - 1]);
} else {
secondLargest = Math.max(rightMax, nums[nums.length - 2]);
}
return secondLargest;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
System.out.println(findSecondLargest(nums)); // 输出:4
}
}
```
**2. 找到数组中的第k小的元素 (快速选择算法,也是基于分治)**
```java
import java.util.Arrays;
public class kthSmallest {
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
public static void quickSelect(int[] arr, int k, int low, int high) {
if (low == high) return arr[low]; // base case
int pivotIndex = partition(arr, low, high);
if (k == pivotIndex) return arr[k];
else if (k < pivotIndex) return quickSelect(arr, k, low, pivotIndex - 1);
else return quickSelect(arr, k, pivotIndex + 1, high);
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int k = 4;
int result = quickSelect(nums, k - 1, 0, nums.length - 1); // 函数下标从0开始
System.out.println("The " + k + "th smallest element is: " + result); // 输出:4
}
}
```