用Java写 1.若数组中有一半以上的元素相同，设计一个算法，找到这个元素并输出。例如数组a[]={1,2,3,2,2,4,1,2,2}，其中2是超过一半相同的元素，算法结果输出2。 2.设计一个分治算法，在一个具有n个元素的数组中，寻找第2大元素。

在Java中，解决这两个问题可以分别采用不同的算法策略： 1. **找出数组中有一半以上元素相同的元素**: 可以使用哈希表（HashMap）来辅助统计每个元素出现的次数。遍历数组，每遇到一个元素就将其添加到哈希表中，同时更新其计数。然后再次遍历数组，检查哈希表中每个元素的计数，如果发现有一个计数大于数组长度的一半（向下取整），那么它就是所求的元素。以下是简单的代码示例： ```java import java.util.HashMap; import java.util.Map; public class Main { public static void main(String[] args) { int[] a = {1, 2, 3, 2, 2, 4, 1, 2, 2}; findMajorityElement(a); } public static int findMajorityElement(int[] nums) { Map<Integer, Integer> countMap = new HashMap<>(); for (int num : nums) { countMap.put(num, countMap.getOrDefault(num, 0) + 1); } for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) { if (entry.getValue() > nums.length / 2) { return entry.getKey(); } } throw new IllegalArgumentException("No majority element found"); } } ``` 运行此程序会输出 `2`。 2. **寻找数组中的第二大的元素（分治法）**: 这是一个经典的二分查找问题变种，可以用递归的方式实现。首先将数组分为两部分，递归地在左右两个部分中寻找最大值和次大值，然后再比较整个数组的最大值和中间部分的最大值即可。以下是代码示例： ```java public class Main { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5}; System.out.println(findSecondLargest(arr)); } public static int findSecondLargest(int[] arr) { if (arr.length < 2) { throw new IllegalArgumentException("Array must have at least two elements"); } return findSecondLargestHelper(arr, 0, arr.length - 1); } private static int findSecondLargestHelper(int[] arr, int left, int right) { if (left == right) { return arr[left]; } int mid = (left + right) / 2; int max1 = findMax(arr, left, mid); int max2 = findMax(arr, mid + 1, right); return Math.max(max1, max2); } private static int findMax(int[] arr, int start, int end) { int max = arr[start]; for (int i = start + 1; i <= end; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } } ``` 运行此程序会输出 `4` 对于给定的数组 `{1, 2, 3, 4, 5}`。