6-3 Duplicated Numbers 分数 10 作者 翁恺 单位 浙江大学 This program reads a lot of integers, in which may be duplicated numbers. The program picks out all the duplicated ones and sorts the remainders in a descendent order. 函数接口定义： public static ArrayList<Integer> pick(ArrayList<Integer> a); a is the ArrayList to be parsed and returns the result as an ArrayList. Hint: These classes and functions may be used. Collection Collections.sort(Collection); Collection Collections.reverse(Collection) 裁判测试程序样例： import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.Scanner; public class Main { /* 请在这里填写答案 */ public static void main(String[] args) { ArrayList<Integer> lst = new ArrayList<>(); Scanner in = new Scanner(System.in); while ( in.hasNextInt() ) { lst.add(in.nextInt()); } lst = pick(lst); for ( int x:lst) { System.out.print(x+" "); } System.out.println(); in.close(); } } 输入样例： 1 1 2 3 4 5 9 3 输出样例： 9 5 4 3 2 1

题目描述

给定一个整数列表，其中可能包含重复的数字。编写一个程序来选择出所有重复的数字，并按降序排序剩余数字。

函数接口定义：

public static ArrayList<Integer> pick(ArrayList<Integer> a);

输入格式

输入包含若干个整数。

输出格式

输出所有重复的数字，并按降序排序剩余数字。

样例输入

1 1 2 3 4 5 9 3

样例输出

9 5 4 3 2 1

算法1

(哈希表) $O(n)$

1.使用哈希表记录每个数出现的次数

2.遍历哈希表，统计出现次数大于1的数字

3.将统计后的数字排序并返回结果

时间复杂度

$O(nlogn)$

参考文献

python代码

java代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

相关问题

6-3 Duplicated Numbers 分数 10 作者 翁恺 单位 浙江大学 This program reads a lot of integers, in which may be duplicated numbers. The program picks out all the duplicated ones and sorts the remainders in a descendent order. 函数接口定义： public static ArrayList<Integer> pi

ecewiseDuplicatedNumbers(int[] nums)

其中，
输入参数：
int[] nums ：整型数组，表示输入的一组整数。
输出参数：
ArrayList<Integer> ：整型数组列表，表示所有重复出现过的整数，按照降序排列。

示例：
输入：nums = {3, 1, 2, 3, 4, 5, 2, 4}
输出：[4, 3, 2]

解释：其中，4、3、2 都是重复出现过的整数，按照降序排列后，输出为 [4, 3, 2]。

算法思路：
1. 使用HashMap记录每个数字出现的次数；
2. 遍历HashMap，将出现次数大于1的数字加入到ArrayList中；
3. 对ArrayList进行降序排列，返回结果。

Java代码实现：

Duplicated Numbers 分数 10 作者 翁恺 单位 浙江大学 This program reads a lot of integers, in which may be duplicated numbers. The program picks out all the duplicated ones and sorts the remainders in a descendent order. 函数接口定义： public static ArrayList<Integer> pick(ArrayList<Integer> a); a is the ArrayList to be parsed and returns the result as an ArrayList. Hint: These classes and functions may be used.

To solve this problem, you can use a HashMap to store the frequency of each number in the ArrayList. Then, iterate through the HashMap to find the numbers that occur more than once and add them to a new ArrayList. Finally, sort the new ArrayList in descending order using Collections.sort() with a custom comparator.

Here's an implementation:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class DuplicatedNumbers {
    public static ArrayList<Integer> pick(ArrayList<Integer> a) {
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : a) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        ArrayList<Integer> duplicatedNumbers = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            if (entry.getValue() > 1) {
                duplicatedNumbers.add(entry.getKey());
            }
        }

        Collections.sort(duplicatedNumbers, (a1, a2) -> a2 - a1);
        return duplicatedNumbers;
    }
}