AC Java solution without set or dictionary. Sort the nums and record the positions


  • 20
    L

    public class Solution {

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    	if(nums.length<2||k<1||t<0) return false;
    	ValuePosPair[] valPosArr = new ValuePosPair[nums.length];
    	for(int i =0;i<nums.length;i++) valPosArr[i] = new ValuePosPair(nums[i],i); 
    	Arrays.sort(valPosArr);	
    	for(int i=0;i<valPosArr.length;i++){
    		for(int j=i+1;j<valPosArr.length&&((long)valPosArr[j].val-(long)valPosArr[i].val<=(long)t);j++){
    			if(Math.abs(valPosArr[j].pos-valPosArr[i].pos)<=k) return true;	
    		}
    	}
    	return false;
    }  
    

    }

    class ValuePosPair implements Comparable<ValuePosPair>{
    
    	int val;
    	int pos;
    
    	ValuePosPair(int v, int p) { val = v; pos = p;}
    
    	public int compareTo(ValuePosPair x){
    		return this.val - x.val;
    	}	
    }

  • 0
    V

    is this accepted, my logic is the same but its timing out


  • 0
    L

    Yes it got AC. I guess you might not do the inner loop like this

    for(int j=i+1;j<valPosArr.length&&((long)valPosArr[j].val-(long)valPosArr[i].val<=(long)t);j++)
    

    to break the inner loop as long as the difference is too big. If this is not the problem, maybe you could paste your code here and we try to figure it out.


  • 0
    V

    Why i can't just compare their value and then judge(Time exceeding(╯﹏╰)) ?Why we have to sort by the value and then compare their pos?Is there any difference?


  • -1
    L

    Hi VictorLees, in my opinion, since the problem is called "Contains Duplicate III", the parameter t would be relatively small and k could be very large. So if we sort the value first, the inner loop may break very fast and get rid of time exceeding.


  • 0
    A

    So this has a runtime of O(n^2), right ? Because of the two nested for loops ..


  • 0
    L

    Hi @ahmadka, we couldn't say this to be O(n^2), it's proper to say this to be O(tn) for the nested for loops and O(nlgn) for the sort process.


  • 0
    M

    use binary search in nested loop can make it o(nlogn)


  • 0
    M

    this one should be o(nlogn)

    class ValuePosPair implements Comparable<ValuePosPair>{
    long val;
    int pos;
    ValuePosPair(long v, int p) { val = v; pos = p;}
    public int compareTo(ValuePosPair x){
    return this.val - x.val > 0 ? 1 : (this.val - x.val == 0 ? 0 : -1);
    }
    }

    //o(nlogn) sort took o(nlogn) and n binary searchs so o(nlogn)
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(nums.length < 2 || k < 1 || t < 0) return false;
        ValuePosPair[] valPosArr = new ValuePosPair[nums.length];
        for(int i = 0; i < nums.length; i++) valPosArr[i] = new ValuePosPair(nums[i],i);
        Arrays.sort(valPosArr);
        for(int i = 0; i < valPosArr.length; i++){
            // for(int j = i + 1; j < valPosArr.length && ((long)valPosArr[j].val - (long)valPosArr[i].val <= (long)t); j++) if(Math.abs(valPosArr[j].pos - valPosArr[i].pos) <= k) return true;
            int id = search(valPosArr, i, nums.length, valPosArr[i].val + t);
            if(id != -1 && id - 1 != i && id - 1 >= 0 && id - 1 < nums.length && Math.abs(valPosArr[i].pos - valPosArr[id - 1].pos) <= k) return true;
        }
        return false;
    }
    // first value > t, r is len
    int search(ValuePosPair[] vs, int l, int r, long t){
        if(l > r) return -1;
        if(l == r) return vs[l].val > t ? l : -1;
        while(l < r){
            int m = l + (r - l) / 2;
            if(vs[m].val <= t) l = m + 1;
            else r = m;
        }
        return r;
    }

Log in to reply
 

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