Short, compare nums[i] with nums[i^1]


  • 16

    Simply find the first index whose "partner index" (the index xor 1) holds a different value.

    Ruby:

    def single_non_duplicate(nums)
      nums[(0..nums.size).bsearch { |i| nums[i] != nums[i^1] }]
    end
    

    Python

    def singleNonDuplicate(self, nums):
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) / 2
            if nums[mid] == nums[mid ^ 1]:
                lo = mid + 1
            else:
                hi = mid
        return nums[lo]
    

    Java:

    public int singleNonDuplicate(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (nums[mid] == nums[mid ^ 1])
                lo = mid + 1;
            else
                hi = mid;
        }
        return nums[lo];
    }

  • 0
    C

    What is the meaning of partner index? Why is it useful here? Thx


  • 1
    P

    @chamberlian1990 , if mid is even, add 1 to make it odd, or if it is odd, decrease it by one.

    [1,1,2,2,3].. then our mid = 2 (index 2 not value). Then we need to check for index 3 which is (10 ^ 1)b.
    if our mid was index 3, then doing 3 = (11) ^ 1 = 10b = 2;


  • 1
    F

    @chamberlian1990 every 2 numbers are partner. (even,odd), (even,odd).
    If mid is even, it's partner is next odd, if mid is odd, it's partner is previous even.


  • -1
    R
    #include<bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        int a[2]={0},res=0;
          while(cin>>a[0] && cin>>a[1])
           {
                  if(a[0]!=a[1])
                       {res=a[0];}
    
           }
           cout<<res;
        return 0;
    }
    
    

    can this be solution in c++?


Log in to reply
 

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