专栏首页菩提树下的杨过算法练习(4)-数组去重合并

算法练习(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个有效值,取出来排序。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Silverlight:利用Panel实现自定义布局

    虽然Silverlight提供了几种基本的布局方式,比如Canvas,Grid,StackPanel,Border...,但有时候可能仍然会觉得不够用。 这时候...

    菩提树下的杨过
  • 数据结构与算法C#版笔记--查找(Search)

    做数据库开发的程序员,可能每天都会处理各种各样的查询sql,这个就是查找(Search)。通过查询记录主键字段(即主关键码)或其它非唯一字段(即次关键码)找到所...

    菩提树下的杨过
  • ArraySegment<T>泛型结构示例

    以下代码利用ArrarSegment泛型结构,从int数组arr中取出arr[2]到arr[5] using System; using System.Col...

    菩提树下的杨过
  • 1089 狼人杀-简单版 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 快乐AC三道题---第一周

    我们要解决的无非是是否把下一个元素加入,是否开始维护一个新的子段。我们开一个数组b[] , 记录b[i],表示以a[i]结尾的全部子段中 最大的那个的 和。 这...

    用户7727433
  • ECJTUACM16 Winter vacation training #4 题解&源码

    https://vjudge.net/contest/149692#overview 这周一VJ比赛,题解&源码已完成! A.....................

    Angel_Kitty
  • 数组问题

    输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字...

    大学里的混子
  • POJ Test for Job(DAG上拓扑排序)

           题意是给了n个点,m条边(单向边),然后每个点都有一个点权(存在负权),问从入度为0的点开始到出度为0的点,最大的权值和为多少。

    Ch_Zaqdt
  • leetcode 204题求素数个数

    Count the number of prime numbers less than a non-negative number, n

    用户1539362
  • POJ 3020 Antenna Placement(二分图最小边覆盖)

           题意是有一个n*m的地图,图中'*'表示城市,现在要给每个城市覆盖无线,需要安装基站,每个基站最多只能覆盖相邻的两个城市,也就是1*2或者2*1的...

    Ch_Zaqdt

扫码关注云+社区

领取腾讯云代金券