（Java）【深基9.例1】选举学生会

一、题目描述

学校正在选举学生会成员，有 $n(n\le 999)$ 名候选人，每名候选人编号分别从 1 到 $n$，现在收集到了 $m(m<=2000000)$ 张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

二、输入格式

输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字。

三、输出格式

求出排序后的选票编号。

四、样例输入

5 10
2 5 2 2 5 2 2 2 1 2

五、样例输出

1 2 2 2 2 2 2 2 5 5

六、失败经历

• 乍一看这个题目，感觉好简单啊，一个Arrays类的sort方法就可以解决了，结果并不然，第一次尝试虽然对了，但没有完全对，用sort方法超时了啊啊啊！

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] number = new int[m];
        for (int i = 0; i < m; i++) {
            number[i] = sc.nextInt();
        }
        Arrays.sort(number);
        for (int i = 0; i < m; i++) {
            System.out.print(number[i] + " ");
        }
    }
}

• 然后使用了StringBuffer解决了超时问题，结果又超内存了。。。。。。我炸了
  其实这次已经接近正确答案了，只需将数组的大小再变小一点点就行了

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n + 1];
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            a[sc.nextInt()]++;
        }
        StringBuffer s = new StringBuffer();
        for (int i = 1; i < n + 1; i++) {
            while (a[i]-- != 0){
                s.append(i + " ");
            }
        }
        System.out.println(s);
    }
}

七、正确代码

经过多次试错，正确答案出现啦！

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] a = new int[sc.nextInt()];
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            a[sc.nextInt() - 1]++;
        }
        StringBuffer s = new StringBuffer();
        for (int i = 0; i < a.length; i++) {
            while (a[i]-- != 0){
                s.append(( i + 1 ) + " ");
            }
        }
        System.out.println(s);
    }
}

八、正确思路及易错点

（1）题目分析

看题目要求：把选票按照投票数字从小到大排序，而投票数字就是候选人的编号，故该题的意思可理解为把选票按照候选人编号从小到大排序

（2）思路分析

①定义一个数组，数组的下标减去一对应了候选人的编号，数组的内容用来存储每个候选人获得了多少票数。

注意点：由于候选人的编号是从1开始的，而数组下标是从0开始的，我们用a[0]存储1号候选人的得票数，a[1]存储2号候选人的得票数，a[n - 1]存储n号候选人的得票数。此时数组的大小为n

int[] a = new int[sc.nextInt()];

②使用循环进行遍历，统计每个候选人获得的票数

具体思路：每读到某个候选人的编号，就将此编号减一作为下标，读取数组中此下标对应的内容，使其自增1，起到统计候选人票数的效果，题目中提供了一共有m张选票，故总共需要读取m次。

for (int i = 0; i < m; i++) {
    a[sc.nextInt() - 1]++;
}

此时就完成了数组的下标减一对应候选人的编号，数组的内容存储以该下标作为编号的候选人获得了多少票数

③创建字符串缓冲区对象,用于存储数据（StringBuffer类的具体使用在下方）

StringBuffer s = new StringBuffer()

④由于上面数组采取一一对应的存储方式，使得数组下标减去一就是候选人的编号，所以我们只需从下标0到下标n利用for循环遍历数组，再利用while循环控制存储次数。

例如下标1对应的数组内容是7，即2号候选人有7票，即a[1] = 7,满足a[1] – != 0 条件的情况有7种，即可以循环7次， s.append(( i + 1 ) + " ")也就可以执行7次，s中也就存储了7次2

关于存储，是利用了字符串缓冲区对象s来存储选票以及追加空格，用StringBuffer才不会超时和超内存

        for (int i = 0; i < a.length; i++) {
            while (a[i]-- != 0){
                s.append(( i + 1 ) + " ");
            }
        }

⑤最后输出就可以啦

System.out.println(s);

（3）StringBuffer: 线程安全的可变字符串

①StringBuffer类概述

• 当对字符串进行拼接操作时，每次拼接都会构成一个新的String对象，既耗费时间又浪费空间。故当一个字符串的内容需要被经常改变时就要使用StringBuffer。
• StringBuffer与String的不同在于：String类是字符串常量，是不可更改的常量。而StringBuffer是字符串变量，它的对象是可以扩充和修改的。

②StringBuffer对象的初始化

StringBuffer s = new StringBuffer();

③StringBuffer类支持的主要方法

④StringBuffer类中和 String 类类似的方法