存在重复元素III[利用排序后的有序性进行剪枝]

前言

当时间复杂度在O(NlongN || N²)时，没有特别要求的情况下，排个序对时间复杂度是毫无影响的，甚至还能拿排完序后的有序性来剪枝，降低运行时间。
不是只有DFS能剪枝，在很多操作中多存在剪枝思想。

一、存在重复元素III

二、排序+剪枝

package everyday.medium;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

// 存在重复元素III
public class ContainsNearbyAlmostDuplicate {
    
    /* target：给定下标的限定范围，元素差值的限定范围，求是否存在这样的 数对。 */
    // 暴力
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    
        int n = nums.length;
        for (int i = 0; i < n; i++) {
    
            for (int j = i + 1; j < n; j++) {
    
                if (Math.abs((long) i - j) <= k
                        && Math.abs((long) nums[i] - nums[j]) <= t)
                    return true;
            }
        }
        return false;
    }
}

// 非暴力,巧解：先排序，然后靠着有序来剪枝。（注：反正对于O(NlogN || N2)的时间复杂度，排个序完全每任何影响。）
class ContainsNearbyAlmostDuplicate2 {
    
    /* target：给定下标的限定范围，元素差值的限定范围，求是否存在这样的 数对。 */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    
        List<int[]> arr = new ArrayList<>();
        int idx = 0;
        for (int num : nums) arr.add(new int[]{
    idx++, num});
        arr.sort(Comparator.comparingInt(o -> o[1]));
        // 爆搜 + 剪枝
        for (int i = 0; i < arr.size() - 1; i++) {
    
            // 注:其实 j = i + 1也就算第一个剪枝了。
            for (int j = i + 1; j < arr.size(); j++) {
    
                int[] a = arr.get(i), b = arr.get(j);

                if (Math.abs((long) a[1] - b[1]) <= t
                        && Math.abs((long) a[0] - b[0]) <= k) return true;
                // 类似剪枝。
                if (Math.abs((long) a[1] - b[1]) > t) break;
            }
        }
        return false;
    }

}

总结

1）剪枝思想存在很多操作中，不仅仅是DFS。
2）排序什么时候大胆用？有序性是个好条件。

参考文献

[1] LeetCode 存在重复元素III