Single Number


  • 0
    A

    Click here to see the full article post


  • 1
    C

    in 1st approach , there is no need for maintaining no_duplicate_list as 2 for loops can be run to check if num is in the array again. So it is O(n^n) time complexity and O(1) space complexity, this is to be further improved by hashing the values in array thus leading to O(n) time and O(n) space, as done in the 2nd approach.

    There is always an equal time gain at the cost of space I believe.


  • 0
    C

    public int singleNumber(int[] nums) {
    Arrays.sort(nums);
    for(int i=0;i<nums.length-1;i+=2){
    if(nums[i]!=nums[i+1])return nums[i];
    }
    return nums[nums.length-1];
    }


  • 0
    L
    This post is deleted!

  • 1
    P
    //Provide a C sample code using XOR method. Submission Accepted.
    int singleNumber(int* nums, int numsSize){
        int x=0;
        for ( int i=0; i < numsSize; i++){
            x = x^nums[i];
            printf("%d\n", x);
        }
        return x;
    }

  • 0

    how to sumbmit the answer


  • 0
    L

    ruby one-liner nums.inject(&:^) dab


  • 0
    T

    class Solution {
    public:
    int singleNumber(vector<int>& nums) {
    int sum=0;
    for(int x=0;x<nums.size();x++)
    sum^=nums[x];
    return sum;
    }
    };


  • 0
    B

    Python:

    from collections import Counter
    
    Counter(nums).most_common()[-1][0] # Create Hash Map with counts. Take last value and return key.
    

  • 0
    0

    well... if it's a list object in python
    you can use list.count(element) to get the count of the element.
    I try to use it in this question, and the result shows 'Time Limit Exceeded".


  • 0
    C
    class Solution(object):
        def singleNumber(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return reduce(lambda x, y: x ^ y, nums)
    

  • 0
    R
    class Solution {
        public int singleNumber(int[] nums) {
           
            int result = -1;
            Set<Integer> set = new HashSet();
            for(int num: nums) {
               if (set.contains(num)) {
                   set.remove(num);
               } else {
                   set.add(num);
               }
            }
           
            for(Integer elem: set) {
                result = elem;
            }
             return result;
        }
        
     }
    

    Time Complexity: O(n*1) = O(n)
    Space Complexity: O(n)


  • 0
    S

    class Solution {
    public int singleNumber(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for(int i=0;i<nums.length;i++){
    if(set.contains(nums[i])){
    set.remove(nums[i]);
    }
    else{
    set.add(nums[i]);
    }
    }
    int result = 0;
    Iterator<Integer> it = set.iterator();
    while(it.hasNext()){
    result = it.next();
    }
    return result;
    }
    }


  • 0
    A

    def singleNumber(nums):
    freq = {}
    for i in nums:
    freq[i] = freq.get(i,0)+1
    for x in freq.keys():
    if freq[x] == 1:
    print x


  • 0
    G

    class Solution {
    public int singleNumber(int[] nums) {
    int x=0;
    for(int i=0;i<nums.length;i++)
    {
    x=x^nums[i];
    }
    return x;

    }
    

    }


  • 0
    V

    public int singleNumber(int[] nums) {
    int bit = nums[0];
    for (int ii = 1; ii < nums.length; ii++) {
    bit = bit ^ nums[ii];
    }
    return bit;
    }


  • 0
    H

    /code public int singleNumber(int[] nums) {
    int singleOne = nums[0];

        for(int i = 1; i<nums.length; i++) {
            singleOne ^= nums[i];
        }
        
        return singleOne;
    }

  • 0
    W
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i=i+2){
            if(i+1<nums.length){
                if(nums[i]!=nums[i+1]){
                    return nums[i];
                }
            }else{
                return nums[i];
            }
        }
        return 0;

  • 0
    S
    def singleNumber(self, nums):
        """
        This code should be able to handle any size of number,
          any size of array so long as you can swap numbers reasonably,
          uses O(1) space,
          and runs in O(n).
        It's a modification of the kth element algo. (selection algo.).
        Also, it's such a pain to program this on the fly...tell me what you think.
    
        :type nums: List[int]
        :rtype: int
        """
        import random
        
        def partition(nums, l, r):
            # use random to avoid dups for pivot (especially required when we get the highest or lowest number and we get stuck in inf loop)
            ri = random.randint(l, r)
            nums[r], nums[ri] = nums[ri], nums[r]
            
            p = nums[r]
            j = l  # first greater than p offset
            for i in range(l, r):
                if nums[i] <= p:
                    nums[j], nums[i] = nums[i], nums[j]
                    if nums[j] == p:
                        nums[l], nums[j] = nums[j], nums[l]
                    j+=1
            nums[r], nums[j] = nums[j], nums[r]  # put the pivot in the position j (which is the left-most number which is > p)
            
            return j  # j is the partition's pivot offset
    
        def run(nums, l, r):
            if l==r:
                return nums[l]
            else:
                p = partition(nums, l, r)  # p is last <= nums[p] value
                if (r - p) % 2 == 1:  # if the right side has an odd number of nums, the odd one out is there
                    return run(nums, p+1, r)
                else:
                    return run(nums, l, p)
                
        return run(nums, 0, len(nums)-1)

  • 0
    Y

    The prompt for this problem is somewhat misleading.
    "Given an array of integers, every element appears twice except for one. Find that single one." Here, I could understand this sentence as the exception integer appears more than twice (or only once as the solution seems to assume here) However, if the exception integer appears more than twice, Approach #3 is not working.


Log in to reply
 

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