Simple Java O(n) solution - HashSet


  • 10

    Idea is to compute the sum mathematically first, and subtracting the elements from it.
    Find the duplicate element, and add that to sum.

    public int[] findErrorNums(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int duplicate = 0, n = nums.length;
        long sum = (n * (n+1)) / 2;
        for(int i : nums) {
            if(set.contains(i)) duplicate = i;
            sum -= i;
            set.add(i);
        }
        return new int[] {duplicate, (int)sum + duplicate};
    }

  • 0
    L

    What is the guarantee that sum + duplicate will always give the missing element?


  • 1

    @lkjhgfdsa After subtracting all elements from expected 'sum', the value is nothing but (missing element - duplicate).
    Here the guarantee is that only one duplicate exists, and only one missing element.


  • 0

    @lkjhgfdsa said in Simple Java O(n) solution - HashSet:

    What is the guarantee that sum + duplicate will always give the missing element?

    @lkjhgfdsa There's only one missing element and one duplicate. So it'll be missing element.


  • 0

    Nice solution, actually I have the same idea but I think it's not necessary to use hashset or hashmap.
    Here is my code with cpp:

    class Solution {
    public:
        vector<int> findErrorNums(vector<int>& nums) {
            int dup = 0, N = nums.size();
            vector<char> table(N + 1, 0);
            long sum = (N * (N + 1)) / 2;
            for (const auto &n : nums) {
                if (++table[n] == 2)
                    dup = n;
                sum -= n;
            }
            return{ dup, sum + dup };
        }
    };
    

    and another version without sum:

    class Solution {
    public:
        vector<int> findErrorNums(vector<int>& nums) {
            int dup = 0, N = nums.size();
            vector<char> table(N + 1, 0);
            for (const auto &n : nums)
                if (++table[n] == 2)
                    dup = n;
            for (int i = 0, j = N + 1;;) {
                if (!table[++i]) return{ dup, i };
                if (!table[--j]) return{ dup, j };
            }
            return{ 0, 0 };
        }
    };
    

  • 0
    P

    @jaqenhgar set.contains and set.add can be replaced with if(!set.add(i))


  • 0
    X
    public int[] findErrorNums(int[] nums) {
            int twice, miss;
            int n = nums.length;
            int[] hash = new int[n];
            int sum = 0;
            for(int num : nums){
                hash[num-1]++;
                if(hash[num-1] == 2) twice = num;
                sum += num;
            }
            // The missing value is total - (sum - twice).
            miss = n * (n+1)/2 - sum + twice;
            return new int[]{twice, miss};
        }
    

  • -1
    W

    Actually we don't add i to set.
    //set.add(i);


  • -1
    H

    Your method is very delicate.


  • 0
    C
    public int[] findErrorNums(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int n = nums.length;
        int nSum = n*(n+1)/2;
        int dup = 0, sumNoDup = 0;
        for(int x: nums) {
            if(set.contains(x)) dup = x;
            set.add(x);
            sumNoDup += x;
        }
        sumNoDup -= dup;
        return new int[]{dup, nSum-sumNoDup};
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.