Find the result using binary search n*log(n)


  • 0
    H
    #include <vector>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <utility>
    using namespace std;
    class Solution {
    public:
        vector<int> twoSum(vector<int> &numbers, int target);
    	int bsearch(vector<pair<int, int> >& numbers, int target, int pos);
    };
    
    int Solution::bsearch(vector<pair<int, int> >& numbers, int target, int pos)
    {
    	int left = pos;
    	int right = numbers.size();
    	while(left <= right)
    	{
    		int mid = left + (right - left) / 2;
    		if(numbers[mid].first > target){
    			right = mid - 1;
    		}else if(numbers[mid].first < target){
    			left = mid + 1;
    		}else{
    			return mid;
    		}
    	}
    	return -1;
    }
    vector<int> Solution::twoSum(vector<int> &numbers, int target)
    {
    	vector<pair<int, int> > nums;
    	for(int i = 0; i < numbers.size(); i++){
    		pair<int, int> p;
    		p.first = numbers[i];
    		p.second = i+1;
    		nums.push_back(p);
    	}
    	sort(nums.begin(), nums.end());
    	for(int i = 0; i < nums.size(); i++)
    	{
    		int v = target - nums[i].first;
    		int pos = bsearch(nums, v, i+1);
    		if(pos != -1){
    			vector<int> result;
    			int a = nums[i].second;
    			int b = nums[pos].second;
    			if(a > b){
    				a ^= b;
    				b ^= a;
    				a ^= b;
    			}
    			result.push_back(a);
    			result.push_back(b);
    			return result; 
    		}
    	}
    }

Log in to reply
 

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