本文旨在详细解析一个基于嵌套循环的java数组去重算法，重点阐述了内层循环结束后通过比较`i==j`来判断元素唯一性的核心逻辑。文章将通过代码示例和逐步调试分析，帮助读者透彻理解该算法的工作原理，并探讨其效率及可能的优化方案，以提升代码的可读性和性能。
数组去重：基于嵌套循环的实现原理
在编程中，从数组中找出所有不重复（即“唯一”或“distinct”）的元素是一个常见的需求。本教程将深入探讨一种使用嵌套循环实现的去重算法，并详细解释其内部机制，特别是 if(i==j) 条件的巧妙运用。
该算法的核心思想是：对于数组中的每一个元素 arr[i]，我们都去检查它在当前位置 i 之前是否已经出现过。如果 arr[i] 在 arr[0] 到 arr[i-1] 之间都没有出现过，那么它就是一个新的、唯一的元素。
以下是该算法的Java实现代码：
public class DistinctElement {
public static void main(String[] args) {
int [] arr = {10,10,20,30,10,20,40,30,60,100,10};
int count = 0; // 用于统计唯一元素的数量
// 外层循环：遍历数组中的每一个元素
for(int i = 0; i < arr.length; i++){
int j; // 内层循环的计数器
// 内层循环：检查 arr[i] 是否在 arr[0] 到 arr[i-1] 之间出现过
for(j = 0; j < i; j++){
// 如果找到与 arr[i] 相同的元素，说明 arr[i] 是重复的
if(arr[i] == arr[j]) {
break; // 立即跳出内层循环
}
}
// 核心逻辑：判断 arr[i] 是否为唯一元素
if(i == j) {
System.out.print(arr[i] + " "); // 打印唯一元素
count++; // 增加唯一元素计数
}
}
System.out.println("\n唯一元素总数: " + count);
}
}核心逻辑解析：if(i==j) 的奥秘
理解 if(i==j) 条件是掌握这个算法的关键。让我们一步步剖析：
立即学习“Java免费学习笔记（深入）”；
外层循环 (for(int i=0; i<arr.length; i++)): 这个循环负责遍历数组中的每一个元素。i 代表当前正在检查的元素 arr[i] 的索引。
内层循环 (for(j=0; j<i; j++)): 对于每一个 arr[i]，内层循环的任务是向前检查从 arr[0] 到 arr[i-1] 的所有元素。j 是内层循环的索引，它始终小于 i。
-
内层循环中的 if(arr[i] == arr[j]) { break; }:
- 如果 arr[i] 与之前的任何一个元素 arr[j] 相等，这意味着 arr[i] 是一个重复元素。
- 一旦找到匹配，break 语句会立即终止内层循环。此时，j 的值将是找到匹配时的索引，即 j < i。
-
内层循环结束后的 if(i==j): 这是判断元素是否唯一的关键所在。
- 情况一：i == j (元素是唯一的) 当内层循环 for(j=0; j<i; j++) 完整地执行完毕，并且没有遇到 break 语句时，j 会从 0 递增到 i-1。在循环结束后，j 的值会再次递增到 i（因为循环条件是 j < i，当 j 达到 i 时循环终止）。 这意味着在 arr[0] 到 arr[i-1] 的所有元素中，都没有找到与 arr[i] 相同的元素。因此，arr[i] 是一个到目前为止的唯一元素，应该被打印出来。
- 情况二：i != j (元素是重复的) 如果内层循环因为 arr[i] == arr[j] 条件满足而提前通过 break 语句终止，那么 j 的值将停留在找到匹配时的索引，此时 j 必然小于 i。 这意味着 arr[i] 在之前的元素中已经出现过，它是一个重复元素，不应该被打印。
逐步调试示例
为了更好地理解上述逻辑，我们以数组 arr = {10,10,20,30,10} 为例进行手动追踪：
-
i = 0, arr[0] = 10:
- 内层循环 for(j=0; j<0; j++)：条件 j<0 不满足，内层循环不执行。
- 内层循环结束后，j 的值仍然是 0。
- 判断 if(i==j)：0 == 0 为真。打印 10。count 为 1。
-
i = 1, arr[1] = 10:
- 内层循环 for(j=0; j<1; j++)：
- j = 0: arr[1] (10) == arr[0] (10)。条件为真。
- 执行 break。内层循环终止。
- 内层循环结束后，j 的值是 0。
- 判断 if(i==j)：1 == 0 为假。不打印。
- 内层循环 for(j=0; j<1; j++)：
-
i = 2, arr[2] = 20:
- 内层循环 for(j=0; j<2; j++)：
- j = 0: arr[2] (20) != arr[0] (10)。
- j = 1: arr[2] (20) != arr[1] (10)。
- 内层循环完整执行完毕。j 的值递增到 2。
- 判断 if(i==j)：2 == 2 为真。打印 20。count 为 2。
- 内层循环 for(j=0; j<2; j++)：
-
i = 3, arr[3] = 30:
- 内层循环 for(j=0; j<3; j++)：
- j = 0: arr[3] (30) != arr[0] (10)。
- j = 1: arr[3] (30) != arr[1] (10)。
- j = 2: arr[3] (30) != arr[2] (20)。
- 内层循环完整执行完毕。j 的值递增到 3。
- 判断 if(i==j)：3 == 3 为真。打印 30。count 为 3。
- 内层循环 for(j=0; j<3; j++)：
-
i = 4, arr[4] = 10:
- 内层循环 for(j=0; j<4; j++)：
- j = 0: arr[4] (10) == arr[0] (10)。条件为真。
- 执行 break。内层循环终止。
- 内层循环结束后，j 的值是 0。
- 判断 if(i==j)：4 == 0 为假。不打印。
- 内层循环 for(j=0; j<4; j++)：
最终输出的唯一元素为 10 20 30，总数为 3。
注意事项与性能考量
- 时间复杂度: 该算法使用嵌套循环，对于每个元素 arr[i]，它最多会比较 i 次。因此，在最坏情况下（所有元素都唯一或所有元素都相同），其时间复杂度为 O(N^2)，其中 N 是数组的长度。对于大型数组，这种方法效率较低。
- 空间复杂度: 该算法没有使用额外的存储空间来辅助去重（除了几个变量），因此空间复杂度为 O(1)。
优化方案
对于更大数据量的去重需求，可以考虑以下更高效的方法：
-
使用 HashSet: Java 集合框架中的 HashSet 专门用于存储不重复的元素。将数组元素依次添加到 HashSet 中，HashSet 会自动处理重复项。
- 时间复杂度：平均 O(N)，最坏 O(N^2)（哈希冲突严重时）。
- 空间复杂度：O(N)（需要额外空间存储 HashSet）。
import java.util.HashSet; import java.util.Set; public class DistinctHashSet { public static void main(String[] args) { int [] arr = {10,10,20,30,10,20,40,30,60,100,10}; Set<Integer> distinctElements = new HashSet<>(); for (int element : arr) { distinctElements.add(element); } System.out.println("唯一元素: " + distinctElements); System.out.println("唯一元素总数: " + distinctElements.size()); } } -
先排序再遍历: 如果允许修改原数组或创建新数组，可以先对数组进行排序。排序后，所有相同的元素都会相邻。然后，只需遍历一次排序后的数组，比较相邻元素即可找出唯一元素。
- 时间复杂度：O(N log N) (排序时间) + O(N) (遍历时间) = O(N log N)。
- 空间复杂度：O(1) (如果原地排序) 或 O(N) (如果创建新数组或使用非原地排序算法)。
import java.util.Arrays; public class DistinctSortedArray { public static void main(String[] args) { int [] arr = {10,10,20,30,10,20,40,30,60,100,10}; Arrays.sort(arr); // 对数组进行排序 System.out.print("唯一元素: "); if (arr.length > 0) { System.out.print(arr[0] + " "); int count = 1; for (int i = 1; i < arr.length; i++) { if (arr[i] != arr[i-1]) { // 比较当前元素与前一个元素 System.out.print(arr[i] + " "); count++; } } System.out.println("\n唯一元素总数: " + count); } else { System.out.println("数组为空，无唯一元素。"); } } }
总结
通过本教程，我们深入理解了基于嵌套循环的数组去重算法，特别是 if(i==j) 条件如何巧妙地利用内层循环的完成状态来判断元素的唯一性。尽管这种方法直观且不占用额外空间，但其 O(N^2) 的时间复杂度限制了它在大规模数据处理中的应用。在实际开发中，我们通常会优先选择 HashSet 或先排序再遍历的方法，以获得更好的性能表现。理解不同算法的原理和优缺点，是成为一名优秀开发者的必备技能。
