Java常见面试算法解析：查找重复元素、二分查找与有序数组合并

查找数组中重复元素及其个数

该题目旨在遍历给定数组，统计每个数字出现的次数。常见的解决方案有两种：一是基于朴素的双层循环比较，适合理解底层逻辑；二是利用 HashMap 进行哈希映射，以空间换时间，显著提升效率。

第1步：使用双层循环进行比较

目的：无需额外内存空间，通过嵌套遍历直接计算重复项。

代码实现：

package com.softsec.demo;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class getRepeat {
	// 循环比较处理
	public static void cyclingDemo(int[] arr){
		// 注意：此处假设遍历特定范围，实际场景中需根据数组最大值优化循环边界
		for (int x = 0; x < 10; x++) {
			int count = 0;
			for (int j = 0; j < arr.length; j++) {
				if (x == arr[j]) {
					count++;
				}
			}
			// 仅输出出现过的元素，过滤掉计数为0的情况会更精准
			if (count > 0) {
				System.out.println(x + " -- 重复个数:" + count);
			}
		}
	}

	public static void main(String[] args){
		Random random = new Random();
		int[] arr = new int[20];
		// 生成测试数据
		for (int i = 0; i < 20; i++) {
			arr[i] = random.nextInt(10);
			System.out.print(arr[i]+" ");
		}
		System.out.println();
		cyclingDemo(arr);
	}
}

说明：该方法时间复杂度为 $O(N^2)$（若外层循环固定为0-9则为 $O(9N)$）。需要注意的是，原逻辑中内层循环判断条件可优化，且输出时应排除未出现的数字，以免产生干扰信息。

第2步：使用HashMap集合映射处理

目的：利用键值对存储元素与频次，单次遍历即可完成统计，时间复杂度降低至 $O(N)$。

代码实现：

package com.softsec.demo;
import java.util.HashMap;
import java.util.Map;

public class getRepeat {
	/**
	 * 转成集合处理
	 * @param arr 输入数组
	 */
	public static void mapDemo(int[] arr){
		Map<Integer, Integer> map = new HashMap<>();
		// 遍历数组，构建频率映射
		for (int a = 0; a < arr.length; a++) {
			if (map.get(arr[a]) != null){
				map.put(arr[a], map.get(arr[a]) + 1);
			} else {
				map.put(arr[a], 1);
			}
		}
		// 打印结果
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			System.out.println(entry.getKey() + " -- 重复个数：" + entry.getValue());
		}
	}
	// main方法同上，调用mapDemo(arr)即可
}

结果展示：
例如输入数组包含多个重复值，输出将直接呈现键值对应关系，如 1 -- 重复个数：6。这种方法避免了遗漏统计，也无需预先知道数据的最大值范围。

二分查找算法实现

二分查找（Binary Search）的前提是数组必须有序。它的基本思想是通过不断缩小搜索区间来定位目标值。每次将查找范围减半，直到找到目标或区间为空。其时间复杂度为 $O( ext{log}_2 N)$。

第1步：明确二分查找步骤

1. 确定中间位置：mid = (left + right) / 2（在Java中为防止溢出推荐 left + (right - left) / 2）。
2. 比较大小：
   * 若 key == arr[mid]，查找成功，返回索引。
   * 若 key < arr[mid]，目标在左半区，更新 right = mid - 1。
   * 若 key > arr[mid]，目标在右半区，更新 left = mid + 1。
3. 循环或递归：重复上述过程，直至 left > right 返回 -1（未找到）。

第2步：编写非递归（迭代）版本

目的：避免递归带来的栈空间消耗，适用于大规模数据场景。

public static int searchIterative(int[] arr, int key) {
	int left = 0;
	int right = arr.length - 1;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (key == arr[mid]) {
			return mid;
		} else if (key > arr[mid]) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return -1; // 表示未找到
}

第3步：编写递归版本

目的：代码结构更简洁，但需注意递归深度限制。

public static int searchRecursive(int[] arr, int left, int right, int key) {
	if (left > right) {
		return -1;
	}
	int mid = left + (right - left) / 2;
	if (key < arr[mid]) {
		return searchRecursive(arr, left, mid - 1, key);
	} else if (key > arr[mid]) {
		return searchRecursive(arr, mid + 1, right, key);
	} else {
		return mid;
	}
}

测试示例：
针对有序数组 {1, 20, 23, 24, 35, 46, 77, 78, 99, 100} 查找 78，函数将正确返回索引 7。

合并两个有序数组

这是一道经典的数组操作题，常用于归并排序（Merge Sort）的核心步骤。要求在不破坏原有顺序的情况下，将两个已排序数组合并为一个更大的有序数组。

第1步：理清合并思路

• 创建一个长度为两数组之和的新数组。
• 设置三个指针：分别指向数组M的头部、数组N的头部以及新数组的头部。
• 比较两个原数组当前指针所指元素，将较小者放入新数组，并将对应指针后移。
• 当其中一个数组遍历完后，将另一个数组剩余部分直接拷贝至新数组末尾。

第2步：代码实现

package com.softsec.demo;

public class ArrayMerge {
	/**
	* 数组合并方法
	*/
	public static int[] mergeArray(int arrayM[], int arrayN[]) {
		int[] newArray = new int[arrayM.length + arrayN.length];
		int start = 0, end = 0, k = 0;

		// 核心比较逻辑
		while(start < arrayM.length && end < arrayN.length) {
			if(arrayM[start] <= arrayN[end]) {
				newArray[k++] = arrayM[start++];
			} else {
				newArray[k++] = arrayN[end++];
			}
		}

		// 处理剩余元素
		while(start < arrayM.length) {
			newArray[k++] = arrayM[start++];
		}
		while(end < arrayN.length) {
			newArray[k++] = arrayN[end++];
		}
		return newArray;
	}

	public static void main(String[] args) {
		int[] arrayM = {1,3,5,7,8,9,14,16,21};
		int[] arrayN = {0,10,20,30,40,50};
		int[] result = mergeArray(arrayM, arrayN);
		
		// 打印结果
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < result.length; i++) {
			sb.append(result[i]).append(i == result.length - 1 ? "" : "，");
		}
		System.out.println(sb.toString());
	}
}

结果验证：
输入 M=[1,3,5...], N=[0,10,20...]，输出结果为按从小到大的完全合并序列：
0，1，3，5，7，8，9，10，14，16，20，21，30，40，50。

总结

以上涵盖了Java基础面试中关于数组操作的几个核心算法点：从最基础的遍历统计，到基于分治思想的二分查找，再到多路归并的数组处理。建议在实际编码中注意边界条件（如空数组、单元素数组）的处理，并在面试中清晰阐述时间/空间复杂度的权衡。以上就是Java常见面试算法解析的详细内容的详细内容，更多关于Java算法教程的资料请关注本站其它相关文章！