[LeetCode] 961.重复 N 次的元素（Easy）C语言题解

题目

• 在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次。返回重复了 N 次的那个元素。

---

示例

①示例1

• 输入：[1,2,3,3]
• 输出：3

②示例2

• 输入：[2,1,2,5,3,2]
• 输出：2

③示例3

• 输入：[5,1,5,2,5,3,5,4]
• 输出：5

---

说明

1.4 <= A.length <= 10000
2.0 <= A[i] < 10000
3.A.length 为偶数

①相关话题

• 哈希表

②题目地址

• 961. 重复 N 次的元素 — 力扣网
• 961. N-Repeated Element in Size 2N Array — leetcode

---

解题方法

①哈希表

• 可用数组模拟的哈希表 / uthash 求解，找出重复了 N 次的元素。
• uthash 是一个用 C 语言编写的开源库，使用宏实现了哈希表的增删改查等功能。
• 时间复杂度：O(N)。
• 空间复杂度：O(N)。

②题目技巧

• 在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次，说明有且仅有一个元素重复。
• 所以只需要用哈希表动态查找 出现次数大于一次 的元素。
• 时间复杂度：O(N)。
• 空间复杂度：O(N)。
• 或者用暴力解法找出重复的元素。
• 时间复杂度：O(N^2)。
• 空间复杂度：O(1)。

③终极技巧

• 已知数组中有 N+1 个不同元素，有 N 个相同元素，则排列中要么所有相同的数都不相邻，否则一定存在相同的数相邻的情形。
• 时间复杂度：O(N)。
• 空间复杂度：O(1)。

---

代码详解

• 哈希表

int repeatedNTimes(int* A, int ASize) {
    int hash[10000] = {0};
    
    for (int i = 0; i < ASize; i++)
        hash[A[i]]++;
    for (int i = 0; i < 10000; i++) {
        if (hash[i] == ASize/2)
            return i;
    }
    
    return 0;
}

• uthash

int repeatedNTimes(int* A, int ASize) {
    struct hash {
        int value;
        int count;
        UT_hash_handle hh; 
    };
    
    struct hash *hashTable = NULL;
    
    for (int i = 0; i < ASize; i++) {
        struct hash *h;
        HASH_FIND_INT(hashTable, A+i, h);
        
        if (h)
            h->count++;
        else {
            h = malloc(sizeof(struct hash));
            h->value = A[i];
            h->count = 1;
            HASH_ADD_INT(hashTable, value, h);
        }
                
        if (h->count == ASize/2)
            return A[i];
    }
    
    return 0;
}

• 技巧—哈希表

int repeatedNTimes(int* A, int ASize) {
    int hash[10000] = {0};
    
    for (int i = 0; i < ASize; i++) {
        if (hash[A[i]] == 1)
            return A[i];
        else
            hash[A[i]]++;
    }
    
    return 0;
}

• 技巧—uthash

int repeatedNTimes(int* A, int ASize) {
    struct hash {
        int value;
        // makes this structure hashable.
        UT_hash_handle hh; 
    };
    
    struct hash *hashTable = NULL;
    
    for (int i = 0; i < ASize; i++) {
        struct hash *h;
        HASH_FIND_INT(hashTable, A+i, h);
        
        if (h)
            return A[i];
        else {
            h = malloc(sizeof(struct hash));
            h->value = A[i];
            HASH_ADD_INT(hashTable, value, h);
        }
    }
    
    return 0;
}

• 技巧—暴力解法

int repeatedNTimes(int* A, int ASize) {
    for (int i = 0; i < ASize; i++) {
        for (int j = i+1; j < ASize; j++) {
            if (A[i] == A[j])
                return A[i];
        }
    }
    
    return 0;
}

• 终极技巧

int repeatedNTimes(int* A, int ASize) {
    for (int i = 2; i < ASize; i++) {
        if (A[i] == A[i-1] || A[i] == A[i-2])
            return A[i];
    }
    
    return A[0];
}

---

附录

• 我的个人博客：messi1002.top
• 如有错误或疑惑之处 请联系 [email protected]
• 所有题目解答：fork me on github