题目描述与示例
题目描述
明明生成了N
个 1
至 500
之间的随机整数。请你删去其中重复的数字,即相同的数字只保留一个,把其余相同的数去掉,然后再把这些数从小到大排序,按照排好的顺序输出。
数据范围: 1 ≤ N ≤ 1000
,输入的数字大小 val
满足 1 ≤ val ≤ 500
输入描述
第一行先输入随机整数的个数 N
。 接下来的 N
行每行输入一个整数,代表明明生成的随机数。
输出描述:
输出多行,表示输入数据处理后的结果。
示例 1
输入
3
2
2
1
输出
1
2
说明
输入解释: 第一个数字是 3
,也即这个样例的 N = 3
,说明用计算机生成了 3
个 1
到 500
之间的随机整数,接下来每行一个输入随机数字,共 3
行,也即这 3
个随机数字为:2 2 1
输出解释:2 2 1
中,出现了重复的2
,只需要输出一个2
即可,而且要按照从小到大的顺序输出全部整数,即依次输出1 2
解题思路
这道题直接运用哈希集合不包含重复元素的性质,将每一个整数都加入哈希集合num_set
中。
由于哈希集合是一种无序的数据结构,为了从小到大依次输出所有元素,需要在所有元素输入完毕之后,将哈希集合num_set
转化为列表num_lst
。对列表num_lst
就可以进行排序了,排序完成后,在一个for
循环内依次输出num_lst
中的所有元素即可。
代码
Python
# 题目:2023Q1A-明明的随机数
# 分值:100
# 作者:闭着眼睛学数理化
# 算法:哈希集合
# 代码有看不懂的地方请直接在群上提问
N = int(input())
# 初始化一个哈希集合num_set,用于储存所有不重复元素
num_set = set()
# 遍历N次,依次输入数字
for _ in range(N):
num_set.add(int(input()))
# 哈希集合是无序的数据结构,所以要将哈希集合转化为列表后再排序
num_lst = list(num_set)
# 对列表进行排序
num_lst.sort()
# 遍历num_lst中的所有元素,按照从小到大的顺序依次输出
for num in num_lst:
print(num)
Java
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
HashSet<Integer> num_set = new HashSet<>();
for (int i = 0; i < N; i++) {
num_set.add(scanner.nextInt());
}
ArrayList<Integer> num_lst = new ArrayList<>(num_set);
Collections.sort(num_lst);
for (int num : num_lst) {
System.out.println(num);
}
}
}
C++
“`C++
#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>
int main() {
int N;
std::cin >> N;
<pre><code>std::unordered_set<int> num_set;
for (int i = 0; i < N; i++) {
int num;
std::cin >> num;
num_set.insert(num);
}
std::vector<int> num_lst(num_set.begin(), num_set.end());
std::sort(num_lst.begin(), num_lst.end());
for (int num : num_lst) {
std::cout << num << std::endl;
}
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度:O(NlogN)
。排序所需的时间复杂度。
空间复杂度:O(N)
。哈希集合所占的额外空间。
说明
华为OD机试有三道题⽬,第⼀道和第⼆道属于简单或中等题,分值为 100 分,第三道为中等或困难题,分值为 200分,总分为 400 分。
机试分数越⾼评级越⾼,⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章:华为OD机考须知
关于机考题目汇总可以看这篇文章:华为OD机试真题 2023 A+B+C+D卷 + 2024新卷(Python&Java&C++)⽬录汇总(每⽇更新)