‘壹’ 深入分析数组去重
深入分析数组去重
数组去重是常见的面试考点，本文尝试深入学习，总结并优化数组去重的实现方法。常见方法包括双重循环法、查找元素第一次出现的位置、排序后去重以及使用散列表。
双重循环法直接而直观，创建新数组，逐个比较元素，时间复杂度为 O(n^2)。优化可改为forEach()方法，时间复杂度不变，代码更简洁。
查找元素第一次出现的位置方法从后往前遍历数组，检查元素位置是否首次出现，避免重复，空间复杂度为 O(1)。优化可标记删除元素索引，减少元素搬移操作。
排序后去重方法使用JavaScript自带排序算法，检查前后相邻元素，若不相等则放入新数组。但该方法不适用于对象，因为对象不适合排序，且无法保证引用相同对象的变量相邻。
使用散列表方法，通过对象实现，读取数据时间复杂度为O(1)。对于JavaScript对象，需要改进键名以区分相同值的对象。时间复杂度可达到O(n)。
ES6的Set提供了新的数据结构，简洁高效，支持多种类型的值作为键。不考虑NaN的去重，简单检查元素是否为NaN并进行去重。
lodash的uniq方法源码实现类似于使用Set进行去重，当数组长度大于等于200时，会创建Set并转换为数组去重，小于200时使用双重循环并进行NaN去重。
总结：在开发中，通常处理的数组规模较小，无需过分关注性能问题。在工程实践中，推荐使用ES6的Set转数组方案实现去重，简洁高效。具体场景选择合适的去重方法，考虑“相等”的定义和场景需求，合理选择合适的相等算法。
‘贰’ 除去一个数组中的重复的数据有什么好算法
这个问题的意思是，如果假设一个数组中存在重复的数据项，那么就中保留重复数据项中的一个。也就是说最终输出的结果数组中不容许存在重复数据项，所以因为这里涉及到重复数据项的问题，所以立马想到了集合(Set)这个数据结构，因为它是不容序存在重复数据项的数据结构，
思路1.也就是将数组中的所有元素插入到一个Set中，利用Set的自动剔除重复数据项的功能，将导致所有重复数据项没有办法插入成功，也就是add方法
返回false,然后调用toArray方法，返回这个集合所对应的数组。那么这个数组就是一个没有重复数据项的数组，利用这个方法，通过比较结果数组和
源数组之间的大小，查看源数组中到底是否存在重复数据项。
思路2.除了利用Set这个数据结构不容序存在重复数据项的功能之外，还有一种很容易想到的方法，也就是对整个数组进行排序，然后遍历排序之后的数组，将重复数据项，清除掉。
思路1的实现：
public static int[] noDup(int[] array) {
Set<Integer> set = new
HashSet<Integer>();
for (int i :
array)
set.add(i);
Integer[]
integers = (Integer[]) set.toArray();
int[] result
= new int[integers.length];
for (int i =
0; i < integers.length; i++)
result[i] =
integers[i];
return
result;
}
思路2的实现:
使用快速排序等算法对数组进行排序，这个排序过程不在介绍。假设下面这个算法的输入是一个几经排好序的数组。
for (int i = 0; i < array.length - 1; i++) {
if (array[i]
== array[i + 1]) {
array[i] =
-1;
}
}
通过上面这段代码就能够实现把数组中所有的重复数据项只保留一个，其它的置为-1或者根据实际情况置成其它值。然后遍历数据，删除所有位-1的数据项，并且将数组中包含的记录个数不断减少即可。