Java数组与二维数组算法实战：查找重复元素、矩阵查找与替换空格

一维数组中查找重复数字

在开发或面试场景中，经常需要从一个包含多个整数的数组中识别出重复出现的元素。本题的目标是找出数组中的任意一个重复数字，若不存在则返回-1。

解题思路与步骤

最直观且易于实现的方法是利用排序后的相邻元素特性。当数组有序排列时，任何重复的数字必然位于相邻位置。具体操作步骤如下：

1. 排序数组：使用 Arrays.sort() 对原数组进行升序排列，使相同的数字聚集在一起。
2. 遍历对比：从索引 i = 1 开始遍历至数组末尾。比较当前元素 numbers[i] 与前一个元素 numbers[i - 1]。
3. 判断结果：一旦发现两者相等，即为找到的第一个重复数字，直接返回该值。
4. 结束处理：若循环完整执行未找到重复项，则返回 -1 表示无重复。

关键注意事项

在编写循环时，起始索引必须设为 1。如果从 0 开始，numbers[0] == numbers[-1] 会导致 ArrayIndexOutOfBoundsException 异常。此外，排序会修改原数组顺序，若后续逻辑依赖原数组次序，需先备份数据。

Java 代码实现

import java.util.*;
public class Solution {
    /**
     * 查找数组中的重复数字
     * @param numbers int整型一维数组 
     * @return int整型，重复的数字或-1
     */
    public int duplicate (int[] numbers) {
        // 边界检查：空数组直接返回
        if (numbers == null || numbers.length == 0) {
            return -1;
        }
        
        // 1. 排序数组
        Arrays.sort(numbers);
        
        // 2. 从索引1开始遍历，比较当前与前一个元素
        for(int i = 1; i < numbers.length; i++) {
            if(numbers[i] == numbers[i - 1]) {
                return numbers[i]; // 找到重复，立即返回
            }
        }
        return -1; // 未找到重复
    }
}

二维数组中的目标值查找

给定一个 m x n 的二维数组，每一行从左到右递增，每一列从上到下也递增。请设计一个高效算法，判断数组中是否含有特定整数 target。

解题思路与步骤

由于数组具有单调性，可以使用“对角线搜索”策略，避免逐个扫描导致的 O(m*n) 低效。选择左下角（或右上角）作为起点是关键：

1. 定位起点：将指针初始化为左下角元素 array[n-1][0]。此处上方元素更小，右侧元素更大。
2. 方向判断：
   • 若当前值 大于 target，说明 target 不可能在当前行的右侧，向上移动（行索引减 1）。
   • 若当前值 小于 target，说明 target 不可能在当前列的上方，向右移动（列索引加 1）。
   • 若当前值 等于 target，查找成功，返回 true。
3. 越界检查：在每次移动前或循环条件中确保坐标未超出数组范围。

Java 代码实现

public class Solution {
    public boolean Find(int target, int [][] array) {
        // 1. 处理异常情况：空数组或行列长度为0
        if (array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }
        
        int rows = array.length;
        int cols = array[0].length;
        
        // 2. 初始化起点：左下角 [rows-1, 0]
        int row = rows - 1;
        int col = 0;
        
        // 3. 在有效范围内循环搜索
        while (row >= 0 && col < cols) {
            if (array[row][col] == target) {
                return true; // 找到目标
            } else if (array[row][col] > target) {
                row--; // 当前值太大，向上移动
            } else {
                col++; // 当前值太小，向右移动
            }
        }
        
        return false; // 遍历结束未找到
    }
}

替换字符串中的空格

在实际数据处理中，有时需要将字符串中的空格替换为 URL 编码格式或其他占位符。例如，将每个空格替换为 "%20"。

解题思路与步骤

虽然 Java 提供了丰富的字符串处理方法，但为了展示底层逻辑或利用固定容量预分配，我们可以使用字符数组（char array）进行手动构建，这种方式在执行多次替换操作时通常比反复拼接字符串更高效。

1. 估算容量：创建一个大小为原字符串长度 3倍 的字符数组。最坏情况（全空格）下，每个字符扩展为3个字符，此容量足以容纳所有新字符，避免扩容开销。
2. 遍历填充：使用独立索引 index 指向字符数组当前位置。遍历原字符串：
   • 若字符为空格，依次写入 '%'、'2'、'0'，并将 index 增加 3。
   • 若非空格，直接写入该字符，并将 index 增加 1。
3. 构建结果：使用 new String(char[], offset, length) 构造最终字符串，仅截取实际填充部分（index），丢弃尾部多余空白。

Java 代码实现

import java.util.*;
public class Solution {
    /**
     * 替换字符串中的空格为%20
     * @param s 原始字符串
     * @return 替换后的字符串
     */
    public String replaceSpace(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }
        
        int length = s.length();
        // 预分配最大可能长度（3倍）
        char[] buffer = new char[length * 3];
        int index = 0;
        
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                buffer[index++] = '%';
                buffer[index++] = '2';
                buffer[index++] = '0';
            } else {
                buffer[index++] = c;
            }
        }
        
        // 只取实际使用的部分转为字符串
        return new String(buffer, 0, index);
    }
}

以上就是关于Java数组与二维数组及替换空格实战真题的详细讲解。这些题目涵盖了排序查找、矩阵遍历优化以及字符串内存操作等核心知识点，建议读者结合代码动手实现以加深理解。更多关于Java编程技巧与算法练习的资料请关注本站其它相关文章！