Single Element in a Sorted Array -- LeetCode 540

[Question]
Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: [3,3,7,7,10,11,11]
Output: 10

Note: Your solution should run in O(log n) time and O(1) space.

[Solution]
//--- C++ ---
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l=0, r=nums.size();
        int mid = 0;
        while (l+1<r) {
            mid = (l+r)>>1;
            if (nums[mid]==nums[mid^0x01])
                l = mid+1;
            else
                r = mid;
        }
        return nums[l];
    }
};

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

Reverse Pairs -- LeetCode 493

[Question]

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

Input: [2,4,3,5,1]
Output: 3

Note:

1. The length of the given array will not exceed 50,000.
2. All the numbers in the input array are in the range of 32-bit integer.

[Analysis]
This is a typical problem for Binary Index Tree (BIT). Another solution is to use a BST with a smaller counter in each node -- but this solution will make time complexity O(N*N) for sorted input array. BIT is still a better solution.

[Solution]
class BIT {
    vector<int> nodes;
    int lowbit(int x) { return -x & x; }
public:
    BIT(int n) : nodes(n+1,0) {};
 
    void add(int pos, int val) {
        while (pos<nodes.size()) {
            nodes[pos]+=val;
            pos += lowbit( pos );
        }
    }
 
    int count(int pos) {
        int res =0;
        while (pos>0) {
            res += nodes[pos];
            pos -= lowbit( pos );
        }
        return res;
    }
};

typedef long long LL;

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<pair<LL,int> > sorted;
        for (int i=0; i<nums.size(); i++) {
            sorted.push_back({(LL)nums[i],i+1});
            sorted.push_back({(LL)nums[i]<<1, -i-1});
        }
        sort(sorted.begin(), sorted.end(), [](pair<LL,int>& a, pair<LL,int>& b) {
            return a.first< b.first || a.first==b.first && a.second>b.second;
        });
     
        unordered_map<LL,int> map;
        for (int i=0; i<sorted.size(); i++)
            map[sorted[i].second] = i;
     
     
        BIT tree(sorted.size());
        int res=0;
        for (int i=nums.size()-1; i>=0; i--) {
            res += tree.count(map[i+1]);
            tree.add(map[-i-1]+1,1);
        }
        return res;
    }
};