Question

小哼的学校要建立一个图书角，老师派小哼去找一些同学做调查，看看同学们都喜欢读哪些书。小哼让每个同学写出一个自己最想读的书的ISBN 号。当然有一些好书会有很多同学都喜欢，这样就会收集到很多重复的ISBN 号。小哼需要去掉其中重复的ISBN 号，即每个ISBN 号只保留一个，也就说同样的书只买一本。然后再把这些ISBN 号从小到大排序，小哼将按照排序好的ISBN 号去书店买书。请你协助小哼完成“去重”与“排序”的工作。

输入输出

输入有2 行，第1 行为一个正整数，表示有n 个同学参与调查（n≤100）。第2 行有n个用空格隔开的正整数，为每本图书的ISBN 号（假设图书的ISBN 号在1~1000 之间）。
输出也是2 行，第1 行为一个正整数k，表示需要买多少本书。第2 行为k 个用空格隔开的正整数，为从小到大已排好序的需要购买的图书的ISBN 号。
[Input Example]

10
20 40 32 67 40 20 89 300 400 15

[Output Example]

8
15 20 32 40 67 89 300 400

Solution_1

先将这n 个图书的ISBN 号去重，再进行从小到大排序并输出。
桶排序稍加改动正好可以起到去重的效果，因此我们可以使用桶排序的方法来解决此问题。

import java.util.Scanner;
public class ISBN 
{
    static int N;
    static int count = 0;
    static boolean[] book = new boolean[1001];
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        for(int i=0; i<N; i++)
        {
            int index = sc.nextInt();
            if(book[index] == false)
            {
                count++;
                book[index] = true;
            }
        }
        sc.close();
        System.out.println(count);
        for(int i=1; i<=1000; i++)
            if(book[i])
                System.out.print(i + " ");
    }
}

Solution_2

先从小到大排序，输出的时候再去重。
排序我们可以用冒泡排序或者快速排序。
接下来，要在输出的时候去掉重复的。因为我们已经排好序，所以相同的数都会紧挨在一起。只要在输出的时候，预先判断一下当前这个数a[i]与前面一个数a[i-1]是否相同。如果相同则表示这个数之前已经输出过了，不用再次输出；不同则表示这个数是第一次出现，需要输出这个数。

import java.util.Scanner;
public class ISBN 
{
    static int N;
    static int[] a;
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        a = new int[N];
        for(int i=0; i<N; i++)
            a[i] = sc.nextInt();
        sc.close();
        //冒泡排序
        for(int i=0; i<N-1; i++)
        {    
            for(int j=0; j<N-i-1; j++)
            {    
                if(a[j] > a[j+1])
                {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
        //快排
        quicksort(0, N-1);
        //要买的书的数量
        int count = 1;
        for(int i=1; i<N; i++)
        {
            if(a[i] != a[i-1])
                count++;
        }
        System.out.println(count);
        //要买的书的ISBN编号
        System.out.print(a[0] + " ");
        for(int i=1; i<N; i++)
        {
            if(a[i] != a[i-1])
                System.out.print(a[i] + " ");
        }
    }
    private static void quicksort(int left, int right) 
    {
        if(left > right)
            return;
        int temp = a[left];
        int i = left;
        int j = right;
        while(i != j)
        {
            while(a[j]>=temp && i<j)
                j--;
            while(a[i]<=temp && i<j)
                i++;
            if(i < j)
            {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        a[left] = a[i];
        a[i] = temp;
        quicksort(left, i-1);
        quicksort(i+1, right);
    }
}

方法比较

接下来我们还需要看下数据范围。每个图书ISBN 号都是1~1000 之间的整数，并且参加调查的同学人数不超过100，即n≤100。之前已经说过，在粗略计算时间复杂度的时候，我们通常认为计算机每秒钟大约运行10 亿次（当然实际情况要更快）。因此以上两种方法都可以在1 秒钟内计算出解。如果题目中图书的ISBN 号范围不是在1~1000 之间，而是-2147483648~2147483647 之间的话，那么第一种方法就不可行了，因为你无法申请出这么大的数组来标记每一个ISBN 号是否出现过。另外如果n 的范围不是小于等于100，而是小于等于10 万，那么第二种方法的排序部分也不能使用冒泡排序。因为题目要求的时间限制是1 秒，使用冒泡排序对10 万个数进行排序，计算机要运行100 亿次，需要10 秒钟，因此要替换为快速排序，快速排序只需要100000×log2100000 ≈ 100000×17≈170 万次，这还不到0.0017 秒。