解题思路

由于数字范围较大,使用哈希表更合适:

  1. 使用 存储已出现的数字
  2. 遍历数组,当遇到已存在的数字时,即为重复数字
  3. 避免使用求和方法(可能溢出)

代码

#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()

算法及复杂度

  • 算法:哈希表查找
  • 时间复杂度:,只需要遍历一次数组
  • 空间复杂度:,需要存储已出现的数字