解题思路
由于数字范围较大,使用哈希表更合适:
- 使用 存储已出现的数字
- 遍历数组,当遇到已存在的数字时,即为重复数字
- 避免使用求和方法(可能溢出)
代码
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
// 使用HashSet存储已出现的数字
unordered_set<int> seen;
// 读取输入并查找重复数字
int num;
while(cin >> num) {
if(seen.count(num)) {
cout << num << endl;
return 0;
}
seen.insert(num);
}
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 使用HashSet存储已出现的数字
Set<Integer> seen = new HashSet<>();
// 读取输入并查找重复数字
while(sc.hasNextInt()) {
int num = sc.nextInt();
if(seen.contains(num)) {
System.out.println(num);
return;
}
seen.add(num);
}
}
}
def find_duplicate():
# 使用set存储已出现的数字
seen = set()
# 读取输入并查找重复数字
nums = list(map(int, input().split()))
for num in nums:
if num in seen:
print(num)
return
seen.add(num)
if __name__ == "__main__":
find_duplicate()
算法及复杂度
- 算法:哈希表查找
- 时间复杂度:,只需要遍历一次数组
- 空间复杂度:,需要存储已出现的数字