LeetCode #136 Single Number Solution & Explanation

Klook.com
Post Views: 407

LeetCode Problem

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

You must implement a solution with a linear runtime complexity and use only constant extra space.

LeetCode #136 Examples and Constraints

Solution

I had tried sorting the array first and then finding the different number.

However, that approach couldn’t achieve the required time complexity.

C# Solution

❌First Try– Sort the array first, then perform a simple iteration

public class Solution {
    public int SingleNumber(int[] nums) {
        
        if(nums.Length == 1)
        {
            return nums[0];
        }
        Array.Sort(nums);
        
        for(int i=0;i<nums.Length;i++)
        {
            if(i != nums.Length-1)
            {
                if(nums[i+1]!=nums[i])
                {
                    return nums[i];
                }
                i+=1;
            }
            else
            {
                return nums[i];
            }
        }
        
        return 0;
    }
}

Time Complexity : O(n log n) ➡ caused by the Array.Sort() function

Solution1 – HashSet

public class Solution {
    public int SingleNumber(int[] nums) {
        HashSet<int>set = new HashSet<int>();

        foreach(var num in nums)
        {
            if(set.Contains(num))
            {
                set.Remove(num);
            }
            else
            {
                set.Add(num);
            }

        }

        return set.First();
    }
}

Time Complexity : O(n)

Why do we need to remove the elements that have appeared before? That’s because, except for the different number, all other numbers appear twice. And what remains will be the solution.

Java Solution

Solution1

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();

        for (int num : nums) 
        {
            if (set.contains(num)) 
            {
                set.remove(num);
            } 
            else 
            {
                set.add(num);
            }
        }

        return set.iterator().next();
    }
}

Python3 Solution

Solution1

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        numSet = set()

        for num in nums:
            if num in numSet:
                numSet.remove(num)
            else:
                numSet.add(num)

        return numSet.pop()

JavaScript Solution

Solution1

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    var numSet = new Set();

    for (let num of nums) 
    {
        if (numSet.has(num)) 
        {
            numSet.delete(num);
        } 
        else 
        {
            numSet.add(num);
        }
    }

    return numSet.values().next().value;
};

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Single Number – LeetCode

Some Random post

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *