I think its O(nlogn), why did it give me "Time Limit Exceeded"?


  • 0
    L

    class node{
    public:
    int num;
    int index;
    node(int n, int i): num(n), index(i){};
    };
    bool wayToSort (node n1, node n2) {return n1.num < n2.num;};
    int BinarySearch(vector<node> nodesVector, int key){
    int left = 0, right = nodesVector.size()-1, mid;

    while (left <= right) {
      mid = (int) ((left + right) / 2);
      if (key == nodesVector.at(mid).num) {
    	return nodesVector.at(mid).index;
      }
      else if (key > nodesVector.at(mid).num)
           left = mid + 1;
      else
           right = mid - 1;
    }
    return -1;
    

    };

    class Solution {
    public:
    vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> sum;

        vector<node > nv;
        for(int i=0; i<nums.size(); i++)
           nv.push_back(node(nums.at(i), i+1));
        std::sort(nv.begin(), nv.end(), wayToSort);
    
        for (int i=0; i< nums.size(); i++){
           int lookFor = target-nums.at(i);
           int binVal = BinarySearch(nv, lookFor);
           if((binVal>0) && (i +1 != binVal)){
             sum.push_back(i+1);
             sum.push_back(binVal);
             return sum;
         }
      }
      return sum;
    }
    

    };


Log in to reply
 

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