Find out repeated number in array - cocoder39/coco39_LC GitHub Wiki

easy solutions include using unordered_map to count how many times each number appears (O(n) time and O(n) memory) or sort first then find out repeated number (O(n * log n) time and O(1) memory).

Here is a O(n) time and O(1) memory solution using bit.

  • get upper bound and lower bound, which would not exceed [INT_MIN, INT_MAX]
  • use (INT_MAX - INT_MIN) bits to record each number, the memory complexity is still constant since (INT_MAX - INT_MIN) is just a constant
int main() {
    vector<int> nums = {1, 2, 3, 4, 4, 3};

    int high = INT_MIN;
    int low = INT_MAX;
    for (auto num : nums) {
        low = min(low, num);
        high = max(high, num);
    }

    vector<bool> visited(high - low + 1); //(INT_MAX - INT_MIN) bits is still O(1) memory
    vector<bool> duplicate(high - low + 1);
    for (auto num : nums) {
        if (! visited[num - low]) {
            visited[num - low] = true;
        } else {
            duplicate[num - low] = true;
        }
    }

    int cnt = 0;
    for (auto d : duplicate) {
        cnt = d ? cnt + 1 : cnt;
    }
    cout << cnt << endl;
    return 0;
}
⚠️ **GitHub.com Fallback** ⚠️