明明的随机数

朱雀 2023-06-29 11:00 106阅读 0赞

[https://www.nowcoder.com/practice/3245215fffb84b7b81285493eae92ff0?tpId=37&tqId=21226&tPage=1&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking][https_www.nowcoder.com_practice_3245215fffb84b7b81285493eae92ff0_tpId_37_tqId_21226_tPage_1_rp_ru_2Fta_2Fhuawei_qru_2Fta_2Fhuawei_2Fquestion-ranking]

## 一、题目描述 ##

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作(同一个测试用例里可能会有多组数据，希望大家能正确处理)。

## 二、代码实现 ##

1、使用数组

只用大小与输入规模相同的数组：

import java.util.Scanner;
    import java.util.Arrays;
    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];
                for (int i=0; i<n; i++) {
                    arr[i] = sc.nextInt();
                }
                
                //排序
                Arrays.sort(arr);
    
                //去重 并 输出
                for (int i=0; i<arr.length; i++) {
                    //对于第一个数字，直接输出； 对于i=2..len-1，则当前一个元素不与自己重复时输出
                    if (i == 0 || arr[i] != arr[i-1]) {
                        System.out.println(arr[i]);
                    }
                }
                
            }
            
        }
           
    }

基于计数排序的思想：

关于计数排序可以参考以下链接：

[https://www.cnblogs.com/bqwzx/p/11029264.html][https_www.cnblogs.com_bqwzx_p_11029264.html]

[https://baike.baidu.com/item/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F][https_baike.baidu.com_item_E8_AE_A1_E6_95_B0_E6_8E_92_E5_BA_8F]

由于输入随机数的取值范围为\[1, 1000\]，于是申请一块空间为1001的数组arr，对于输入元素num，让arr\[num\] = 1。

import java.util.Scanner;
    import java.util.Arrays;
    public class Main {
       
        public static void main(String[] args) {
            
            Scanner sc = new Scanner(System.in);
            int[] arr = new int[1001];
            while (sc.hasNext()) {
                int n = sc.nextInt();
                //int[] arr = new int[1001];
                //
                Arrays.fill(arr, 0);
    
                for (int i=0; i<n; i++) {
                    int num = sc.nextInt();
                    //if (arr[num] == 0) {
                        arr[num] = 1;
                    //}
                }
    
                for (int i=0; i<1001; i++) {
                    if (arr[i] == 1) {
                        System.out.println(i);
                    }
                }
            }
            sc.close();
        }
        
    }

2、使用集合

使用ArrayList：

输入时不插入已经存在的元素，也就是实现去重；遍历完成后，对集合进行排序

import java.util.Scanner;
    import java.util.ArrayList;
    import java.util.Collections;
    public class Main {
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            ArrayList<Integer> list = new ArrayList<>();
            while (sc.hasNext()) {
                list.clear();
                
                int n = sc.nextInt();
                //输入时就去重
                for (int i=0; i<n; i++) {
                    int num = sc.nextInt();
                    if (!list.contains(num)) {
                        list.add(num);
                    }
                }
                
                //排序
                Collections.sort(list);
                
                for (int i=0; i<list.size(); i++) {
                    System.out.println(list.get(i));
                }
            }
        }
        
    }

使用TreeSet：

利用TreeSet自带的按值排序插入、去重特性

import java.util.Scanner;
    import java.util.TreeSet;
    import java.util.Set;
    import java.util.Iterator;
    public class Main {
        
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            //Set<Integer> set = new HashSet<>();
            //之所以不用HashSet，是因为HashSet没有排序方法，如ArrayList就有Collections.sort(ArrayList);
            //
            Set<Integer> set = new TreeSet<>();
            while (sc.hasNext()) {
                set.clear();
                
                int n = sc.nextInt();
                //输入时就去重，利用集合自身的去重特性；输入时就排序，利用TreeSet插入时维护值有序的特性
                for (int i=0; i<n; i++) {
                    set.add(sc.nextInt());
                }
                
                Iterator<Integer> it = set.iterator();
                while (it.hasNext()) {
                    System.out.println(it.next());
                }
            }
        }
      
    }

[https_www.nowcoder.com_practice_3245215fffb84b7b81285493eae92ff0_tpId_37_tqId_21226_tPage_1_rp_ru_2Fta_2Fhuawei_qru_2Fta_2Fhuawei_2Fquestion-ranking]: https://www.nowcoder.com/practice/3245215fffb84b7b81285493eae92ff0?tpId=37&tqId=21226&tPage=1&rp=&ru=%2Fta%2Fhuawei&qru=%2Fta%2Fhuawei%2Fquestion-ranking
[https_www.cnblogs.com_bqwzx_p_11029264.html]: https://www.cnblogs.com/bqwzx/p/11029264.html
[https_baike.baidu.com_item_E8_AE_A1_E6_95_B0_E6_8E_92_E5_BA_8F]: https://baike.baidu.com/item/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F