C++ solution without using set::lower_bound


  • 0
    B

    Hi all,

    This is my first time to post code in this Discuss forum.

    The idea is basically heritage from Contains-Duplicate-ii, by offering another way to find duplicates.

    The total time complexity is O(N * min(k, 2log(k)(t + 1)))**, where N is the length of the array.

    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            if (nums.size() < 2)
                return false;
            
            if (k < 0 || t < 0)
                return false;
                
    		return containsNearbyAlmostDuplicateCore(nums, (long long)k, (long long)t);
    	}
    
    private:
    	bool containsNearbyAlmostDuplicateCore(vector<int>& nums, long long k, long long t) {
            //Record the latest (k+1) numbers
            set<int> latestNums;
            latestNums.insert(nums[0]);
            
            for (int i = 1; i < nums.size(); i++) {
                if (i > k) {
                    latestNums.erase(nums[i - k - 1]);
                }
                
    	    if (k == 1 || k < 2 * log(k) * (t + 1)) { //If t is int, 2 * t may overflow, so convert it to long long
    		    for (auto iter = latestNums.begin(); iter != latestNums.end(); iter++) {
                    if (abs((long long)*iter - nums[i]) <= t) {
                            return true;
                        }
                    }
                } else {
                    for (int j = 0; j <= t; j++) {
                        if (latestNums.find(nums[i] + j) != latestNums.end() || latestNums.find(nums[i] - j) != latestNums.end()) {
                            return true;
                        }
                    }
                }
                
                latestNums.insert(nums[i]);
            }
            
            return false;
        }
    };
    

    Note:

    L 24~36:

    k and t may be very big and cause TLE. Need to choose which way to compare according to k and t's value.

    Since L31~36's time complexity is 2 * log(k) * (t + 1), when k == 1 (since log(1) == 0) or k <= 2 * log(k) * (t + 1), try to find duplicate by numbers' indices. Else, try by difference in values.

    L10, L26:

    Watch out for overflows.

    I know this is a bit hacky but it works without dependence of set::lower_bound function.

    Any thoughts?


Log in to reply
 

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