C++ solution with O(nlogn) time complexity


  • 0
    S

    A group of data proved this algorithm is NOT correct. Sorry for that. But is there a O(n logn) algorithm, please?

    step 1: a quick sort.
    step 2: set two indices start and end which locates at the beginning and the end of the num array.
    use binary search to find the newTarget = target - num[start] - num[end] with index of p, if found, return the target directly, else record the minimal difference between the num[start]+num[p]+num[end] and target.
    The loop ends when start >= end - 1

    From the start to the end, n loops exists.
    Each time log(n) for binary search, so the total cost is nlogn.

    class Solution {
        int findTarget(vector<int> &num, int start, int end, int target) {
            if (start==end) {
                return start;
            }
            if (end-start==1) {
                return abs(num[end]-target) > abs(num[start]-target) ? start : end;
            }
            int mid = (start+end)/2;
            if (num[mid]==target)
                return mid;
            else if(num[mid]>target)
                return findTarget(num, start, mid, target);
            else
                return findTarget(num, mid, end, target);
        }
    public:
        int threeSumClosest(vector<int> &num, int target) {
            if (num.size()==0) return 0;
            if (num.size()==1) return num[0];
            if (num.size()==2) return num[0]+num[1];
            if (num.size()==3) return num[0]+num[1]+num[2];
            
            sort(num.begin(), num.end());
            
            int start = 0;
            int end = int(num.size()-1);
            
            int mindiff = INT_MAX;
            while (start<end-1) {
                
                int newTarget = target - (num[start] + num[end]);
                int p = findTarget(num, start+1, end-1, newTarget);
                int curSum = num[start] + num[end] + num[p];
                if (curSum == target) {
                    return target;
                } else if(curSum > target) {
                    mindiff = abs(mindiff)>abs(target-curSum) ? target-curSum : mindiff;
                    end--;
                } else {
                    mindiff = abs(mindiff)>abs(target-curSum) ? target-curSum : mindiff;
                    start++;
                }
            }
            
            return target-mindiff;
        }
    };

  • 3
    L

    what if 1 3 11 14 21 30? for target as 36


  • 0
    D

    in the test above it is proved incorrect
    [1 3 11 14 21 30] 36


  • 0
    A

    the closest three numbers are 1,14,21,not 3,11,21


  • 0
    S

    Yes, I am wrong. I am so sorry for that. But is there a correct O(n logn) method?


Log in to reply
 

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