SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given a non-empty array of integers where every element appears twice except for one. Find that single one.

In a more general scenario, you may need to find all elements that appear exactly once when every other element appears more than once.

Intuition

To solve this problem, the most intuitive approach is to count the occurrences of each element in the array. Once we have the counts, we can easily identify the element(s) that appear exactly once.

Approach

1. Counting Occurrences:

   • Use a data structure like a hash map (or dictionary) to count how many times each element appears in the array.

2. Filtering Results:

   • Once the counts are tallied, filter the map to extract the element(s) that appear exactly once.

3. Return the Result:

   • Return the element(s) that have a count of one.

4. Implementation:

   • In C++, use unordered_map to count occurrences.
   • In Java, use HashMap for counting and ArrayList for the result.
   • In Python, use Counter from the collections module for counting.

Complexity

Time Complexity:

O(n) where n is the number of elements in the input array. Each element is processed once to count the occurrences and then once again to filter the result.

Space Complexity:

O(n) where n is the number of unique elements in the input array. The space is used by the hash map or equivalent data structure to store the counts.

Code

C++

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int, int> countMap;

        // Count the occurrences of each number
        for (int num : nums) {
            countMap[num]++;
        }

        // Find numbers that appear exactly once
        vector<int> result;
        for (const auto& entry : countMap) {
            if (entry.second == 1) {
                result.push_back(entry.first);
            }
        }

        return result;
    }
};

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # Count the occurrences of each number
        countMap = Counter(nums)

        # Find numbers that appear exactly once
        return [num for num, count in countMap.items() if count == 1]

Java

class Solution {
    public int[] singleNumber(int[] nums) {
        HashMap<Integer, Integer> countMap = new HashMap<>();

        // Count the occurrences of each number
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // Find numbers that appear exactly once
        List<Integer> result = new ArrayList<>();
        for (int key : countMap.keySet()) {
            if (countMap.get(key) == 1) {
                result.add(key);
            }
        }

        // Convert List<Integer> to int[]
        int[] output = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            output[i] = result.get(i);
        }

        return output;
    }
}

JavaScript

var singleNumber = function (nums) {
    let countArr = []

    for (let num of nums) {
        const index = countArr.findIndex(item => item.num === num)

        if (index > -1) {
            countArr[index].count++
        } else {
            countArr.push({ num: num, count: 1 })
        }
    }

    return countArr.filter(item => item.count === 1).map(item => item.num)
};