O(n) solution w/ Python & C++


  • 0
    Z

    python solution:

    class Solution(object):
        def findErrorNums(self, nums):
            n = len(nums)
            expect = n * (n + 1) / 2
            actual = sum(nums)
            cnt = [0] * (n + 1)
            for n in nums:
                if cnt[n]:
                    return [n, expect - actual + n]
                cnt[n] += 1
    

    a shorter python solution:

    class Solution(object):
        def findErrorNums(self, nums):
            # @ hy299792458
            s1, s2, n = sum(nums), sum(set(nums)), len(nums)
            return [s1 - s2, n * (n + 1) / 2 - s2]
    

    c++ solution:

    class Solution {
    public:
        vector<int> findErrorNums(vector<int>& nums) {
            int n = nums.size();
            vector<int> counter(n + 1);
            int expect = n * (n + 1) / 2;
            int actual = accumulate(nums.begin(), nums.end(), 0);
            for ( int i : nums ) {
                if ( 1 == counter[i] )
                    return {i, expect - actual + i};
                ++counter[i];
            }
        }
    };
    

  • 0

    This is an 6 lines version: https://discuss.leetcode.com/topic/97091/6-lines-c-solution-with-explanation. It's O(1) space, O(n) time.


Log in to reply
 

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