题目 :
假设顺序表L中的元素按从小到大的次序排列,编写算法删除顺序表中“多余”的数据元素,即操作之后的顺序表中所有元素的值都不相同,要求时间尽可能的少;并对顺序表A(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9)模拟执行本算法,并统计移动元素的次数。
我一开始看见这个题的时候,第一时间想到了"序列去重",然后自然而然想到了使用哈希表哈哈哈,然后这道题就被我搞复杂了,我的复杂思路如下,不建议采用我这种方式解题哦~
要在Java中去除顺序表中的重复元素而不改变元素的原始顺序,可以结合使用哈希表(或HashSet)和ArrayList。HashSet用于追踪已经出现过的元素,而ArrayList用于存储去除重复后的元素。这个方法保持了元素的原始顺序并且去除了重复项。
同时,这个方法的时间复杂度是O(n),其中n是输入数组的长度,因为每个元素只被遍历一次。由于HashSet的添加和查找操作通常是O(1)的,因此这种方法是高效的。
以下就是一个Java代码实现上述的逻辑 :
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class RemoveDuplicates {
public static void main(String[] args) {
// 示例数组
int[] nums = {1,2,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9};
// 调用函数去除重复元素
List<Integer> result = removeDuplicates(nums);
// 打印结果
for (int num : result) {
System.out.print(num + " ");
}
}
public static List<Integer> removeDuplicates(int[] nums) {
Set<Integer> seen = new HashSet<>();
List<Integer> result = new ArrayList<>();
for (int num : nums) {
if (!seen.contains(num)) {
seen.add(num);
result.add(num);
}
}
return result;
}
}
要实现移动元素计数的功能,我们可以引入一个计数器变量来跟踪添加到result数组中的每个元素。每当我们向result中添加一个元素时,就增加这个计数器的值。
问: 为什么移动元素的次数就是最后元素的个数 ?
?
如下 : 修正后的代码(加上了计数器)
public static void removeDuplicates(ArrayList<Integer> arrayList){
HashSet<Integer> key = new HashSet<>();
ArrayList<Integer> result = new ArrayList<>();
int moveCount = 0;
for (int num : arrayList) {
if (!key.contains(num)) {
key.add(num);
result.add(num);
moveCount++; // 增加移动次数
}
}
System.out.println("移动元素的次数: " + moveCount);
for (int num : result) {
System.out.print(num + " ");
}
}
最后我就去搜罗搜罗,发现了非常非常巧妙的方法,没有使用额外的空间,仅仅在原数组上面进行操作就完成了对序列去重的操作,而且还没有改变序列中各个元素的顺序,Java代码如下,光看下面的这几行代码,感觉不是非常直观,所以我还是用图把这个逻辑实现出来,这样理解起来也会更加的容易~
先来对这个代码进行一个逻辑上的解释,我们要知道,这个方法只能用在特定的场景,也就是只能拿来解特定的题目,这里的数组A必须是已经有序的才可以使用.
图示
一步一步拆解的示意图
Java代码
public int distinct(int[] A) {
int t = 0;
for (int i = 0; i < A.length; i++) {
if (i == 0 || A[i] != A[i - 1]) A[t++] = A[i];
}
return t;
}