A C# O(NLogK) Solution by using SortedSet


  • 0
    L

    EDIT: Fix it by using SortedSet.GetViewBetween

    public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(t < 0) return false;
        SortedSet<long> ss = new SortedSet<long>();
        for(int i = 0; i < nums.Length; i++){
            if(ss.GetViewBetween((long)nums[i] - t, (long)nums[i] + t).Count > 0) return true;
            ss.Add(nums[i]);
            if(i >= k) ss.Remove(nums[i - k]);
        }
        return false;
    }
    

    Below is the old version of O(Log(N*K))

    public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        SortedList<int, int> sdc = new SortedList<int, int>();
        for (int i = 0; i < nums.Length && k != 0; i++){
            for (int j = 0, l = sdc.Count - 1; j <= l;)
                if ((long)nums[i] - (long)sdc.Keys[(j + l) / 2]  > (long)t)
                    l = (j + l) / 2 - 1;
                else if ((long)nums[i] - (long)sdc.Keys[(j + l) / 2] < -(long)t)
                    j = (j + l) / 2 + 1;
                else return true;
            if (sdc.Count == k)
               sdc.RemoveAt(sdc.IndexOfValue(i - k));
            sdc.Add(nums[i], i);
        }
        return false;
    }

  • 0

    Looks like O(n^2) to me. Add and RemoveAt are expensive.


  • 0
    L

    remove and add is at O(n) level.
    still thinking how to maintain a K-length window effectively
    C# doesn't have treeset. I don't want to use linq built-in queries too..


  • 0
    L

    inner loop is a binary search


  • 0

    I'm confused. Your title still says O(N*LogK). Do you not think that it's O(n^2) or at least O(nk)?


  • 0
    L

    I don't think it's N*K. the Inner loop is a binary search in a K-Window so it's LogK


  • 0

    Yes, yes, the binary search is fast. Which is why I didn't even mention it. What I did say is "Add and RemoveAt are expensive". They're linear time. And you do them (up to) N times. So you have "linear times linear".


  • 0

    Btw, can sdc.ContainsKey(nums[i]) ever be true? Wouldn't the binary search have succeeded and the function returned?


  • 0
    L

    you are right. I removed that part.


  • 0
    L

    Understand. trying to figure out workaround


Log in to reply
 

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