题意整理

• 输入若干个随机数。
• 将这些随机数去重，并且从小到大排序，然后输出。

方法一（计数）

1.解题思路

• 定义一个计数数组，用于统计每个随机数出现次数。
• 将随机数存放在一个定义好的数组里，然后遍历数组，统计每个数出现次数。
• 遍历随机数的范围，如果某个数出现次数大于等于1，则输出。

动图展示：

2.代码实现

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        //标准输入
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //随机整数的个数
            int n=sc.nextInt();
            //用于存放随机数
            int[] arr=new int[n];
            //计数数组
            int[] count=new int[1001];
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
                //记录随机数出现次数
                count[arr[i]]++;
            }
            for(int i=1;i<=1000;i++){
                //从小到大输出随机数
                if(count[i]>=1){
                    System.out.println(i);
                }
            }
        }
    }
}

3.复杂度分析

• 时间复杂度：需要统计所有随机数出现次数，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度为$O(1)O(1)$。

方法二（TreeSet）

1.解题思路

由于题目的要求是排序和去重，而TreeSet结构刚好满足这个需求，所以直接将所有随机数添加到TreeSet，然后遍历整个TreeSet，输出所有元素即可。

2.代码实现

import java.util.Scanner;
import java.util.TreeSet;

public class Main{
    public static void main(String[] args){
        //标准输入
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //随机数个数
            int n=sc.nextInt();
            //TreeSet结构，用于排序和去重
            TreeSet<Integer> set=new TreeSet<Integer>();
            for(int i=0;i<n;i++){
                set.add(sc.nextInt());
            }
            //直接遍历TreeSet，输出所有元素
            for(Integer i:set){
                System.out.println(i);
            }
        }                     
    }
}

3.复杂度分析

• 时间复杂度：TreeSet添加元素的时间复杂度是$lo{g}_{2}nlog\_2n$，需要添加n个元素，所以时间复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$。
• 空间复杂度：需要额外大小为n的TreeSet，所以空间复杂度为$O(n)O(n)$。