算法练习(4)-数组去重合并
这是日常工程中，经常会遇到的场景，拿到2个list，里面有重复元素，要求去重合并最终排序输出。
题目：2个数组，比如[1,1,6,8] , [6,8,9,1,10,4]，要求合并去重并排序，即最终变成[1,4,6,8,9,10]
思路1 ：TreeSet
实际java工程中，最直观的想法，就是利用现成的集合类TreeSet
public static void main(String[] args) {
int[] a = new int[]{1, 1, 6, 8};
int[] b = new int[]{6, 8, 9, 1, 10, 4};
Set<Integer> set = new TreeSet<>();
for (int i = 0; i < a.length; i++) {
set.add(a[i]);
}
for (int i = 0; i < b.length; i++) {
set.add(b[i]);
}
System.out.println(set);
}全扔进去就完事了，但是从算法角度，并非最优题。TreeSet内部是采用HashMap加其它一堆复杂结构完成的。
思路2：类似桶排序的空间换时间解法
如果已知数值的大小范围，比如0-100，可以预选创建一个长度为100的空数组，每个值默认初始为0，下标索引对应0-100之间的数字。把2个数组跑一次，在相应的索引位置位，值+1，相当于做标识，O(N)就能搞定
public static void main(String[] args) {
int[] a = new int[]{1, 1, 6, 8};
int[] b = new int[]{6, 8, 9, 1, 10, 4};
int[] temp = new int[100];
for (int i = 0; i < a.length; i++) {
temp[a[i]] += 1;
}
for (int i = 0; i < b.length; i++) {
temp[b[i]] += 1;
}
for (int i = 0; i < temp.length; i++) {
if (temp[i] > 0) {
System.out.print(i + "\t");
}
}
}思路3：老老实实的循环遍历
这是最差解法，只是列下思路，先弄1个新数组(大小为2个数组size合)，然后1个个循环，把不重复的依次放入，最后把把前面N个有效值，取出来排序。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读