This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 220 on LeetCode. There is duplicate element III and the difficulty is medium.

Tag: “Sliding window”, “binary”, “bucket sort”

You are given an array of integers nums and two integers k and t.

Abs (nums[I] -nums [j]) <= t, and abs(i-j) <= k.

Returns true if it exists, false if it does not.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0 output: trueCopy the code

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2 Output: trueCopy the code

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3 output: falseCopy the code

Tip:

  • 0 <= nums.length <= 2 *
    1 0 4 10^4
  • –
    2 31 2^{31}     <= nums[i] <=
    2 31 2^{31}     – 1
  • 0 <= k <=
    1 0 4 10^4
  • 0 <= t <=
    2 31 2^{31}     – 1

Sliding window & dichotomy

According to the problem, for any positioni(Suppose its value isu), we actually want the subscript range to be
[ m a x ( 0 . i – k ) . i ) [max(0, i – k), i) Find values in the range within
[ u – t . u + t ] [u – t, u + t] The number of.

A naive idea would be to check k elements later every time you go to any position I, but this would be O(nk)O(nk)O(nk), which would time out.

Obviously we need to optimize the “check the next K elements” process.

We want to use an “ordered set” to maintain lengthkThe number of sliding Windows in which the data structure best supports efficient “query” and “insert/delete” operations:

  • Query: can apply “binary search” in “ordered collection”, quickly find “less than or equal to
    u u     “And” greater than or equal touIs the closest in an ordered setuThe number of).
  • Insert/delete: Adding or removing elements to an ordered collection can be done with less than linear complexity (maintaining the ordered nature).

You might think of a HashMap that approximates O(1)O(1)O(1) operations, Abs (nums[I],nums[j])⩽tabs(nums[I],nums[j]) \ leQslant tabs(nums[I],nums[j])⩽ Nums [I] is not necessarily equal to nums[j], and HashMap does not support “range query” operations well.

We also think of “tree” structures.

AVL, for example, allows us to get the closest value to u at the worst O(log⁡k)O(\log{k})O(logk), but this involves frequent insert/delete operations in addition to “query” (as we traverse nums elements, the sliding window keeps moving to the right, We need to constantly remove and add elements to the “ordered set”).

Simply using AVL trees causes each insertion and deletion operation to trigger a balancing adjustment of AVL, with a balancing adjustment accompanied by several rotations.

Red-black trees solve this problem by limiting the number of rotations caused by balance adjustment from “several” to “at most three.”

Therefore, when the “query” action and the “insert/delete” action are at the same frequency, the better choice is to use a “red-black tree”.

That is, the TreeSet data structure corresponding to Java (based on red-black trees, lookup and insert are half efficient).

Other details: Due to the large number in NUMS, there is an int overflow problem and we need to use long for storage.

Code:

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> ts = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            Long u = nums[i] * 1L;
            // Find the maximum value of u that is less than or equal to u.
            Long l = ts.floor(u); 
            // Find the smallest value greater than or equal to u from ts (the nearest value greater than or equal to u)
            Long r = ts.ceiling(u); 
            if(l ! =null && u - l <= t) return true;
            if(r ! =null && r - u <= t) return true;
            // Add the current number to ts and remove the number outside the subscript range of [Max (0, i-k), I) (keep the sliding window size of k))
            ts.add(u);
            if (i >= k) ts.remove(nums[i - k] * 1L);
        }
        return false; }}Copy the code
  • Time complexity:TreeSetBased on a red-black tree, lookup and insert are both
    O ( log ⁡ k ) O(\log{k})     Complexity. The overall complexity is
    O ( n log ⁡ k ) O(n\log{k})
  • Space complexity: O(k)O(k)O(k)

Bucket sort

The reason why the above solution can’t be linear is that we need to be linear in sizekThe sliding window is located in the “Ordered Collection” anduStudent: Close numbers.

And if we can bring thatkA number divided
k k A bucket, then we can
O ( 1 ) O(1) The complexity of the
[ u – t . u + t ] [u – t, u + t] Check if the target bucket has elements.

Set the bucket size as size=t+1size =t+1size =t+1, and calculate the bucket number according to u:

  • If the bucket already exists, it already exists
    [ u – t . u + t ] [u – t, u + t]     Range of numbers, returntrue
  • If the bucket does not exist, check that the elements of the two adjacent buckets do
    [ u – t . u + t ] [u – t, u + t]     Range of numbers, if anytrue
  • Establishing goals barrels, and remove the subscript range is not [Max (0, I – k), I) [Max (0, I – k), I) [Max (0, I – k), I) inside the barrel

Code:

class Solution {
    long size;
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        Map<Long, Long> map = new HashMap<>();
        size = t + 1L;
        for (int i = 0; i < n; i++) {
            long u = nums[i] * 1L;
            long idx = getIdx(u);
            // If the target bucket already exists (the bucket is not empty), the number in the range of [U-t, u + t] is already in front of it
            if (map.containsKey(idx)) return true;
            // Check the next bucket
            long l = idx - 1, r = idx + 1;
            if (map.containsKey(l) && u - map.get(l) <= t) return true;
            if (map.containsKey(r) && map.get(r) - u <= t) return true;
            // Create the target bucket
            map.put(idx, u);
            // Remove buckets whose subscripts are not in [Max (0, i-k), I)
            if (i >= k) map.remove(getIdx(nums[i - k] * 1L));
        }
        return false;
    }
    long getIdx(long u) {
        return u >= 0 ? u / size : ((u + 1) / size) - 1; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(k)O(k)O(k)

【 Key 】 How to understandgetIdx()The logic of the

  1. whysizeThe need totfor+ 1Operate?

The goal is to make sure that the difference is less than or equal totCan fall into a bucket.

For example 🌰, if [0,1,2,3], t = 3, obviously all four numbers should fall in the same bucket.

If t is not +1, then [0,1,2] and [3] will be dropped into different buckets. In order to solve this problem, we need to add +1 to t as size.

So our number line can be partitioned into:

0 1 2 3 4 5 6 7 | | 8 9 10 11 12 13 14 15 | |...

To sum up, let’ssize = t + 1Is essentially because the difference is zerotThe distance between two numbers on the number line is zerot + 1They need to be dropped into the same bucket.

When has been clear about thesizeFor the positive part, we haveidx = nums[i] / size.

  1. How to understand the logic of the negative part?

Since we’re dealing with the positive number, we’re dealing with the value 0, so we’re starting with negative 1.

T = 3 and size = t + 1 = 4.

In the case of [-4,-3,-2,-1], they should fall in a bucket.

Idx = nums[I] / size [-1,-2,-1] / idx = nums[I] / size

The root cause is that when we deal with integers, we’ve already split the values0.

At this point, we need to be rightnums[i]for+ 1Operation (that is, the negative part is moved to the right as a whole on the number line), i.e(nums[i] + 1) / size.

So the negative part can be divided as well as the positive part.

But since bucket 0 is already in use, we need to build on that- 1, is equivalent to subscript the bucket of the negative part (idxIf you move to the left, you get((nums[i] + 1) / size) - 1.

The last

This is the no.220 of our “Brush through LeetCode” series. The series started on 2021/01/01, and there are 1916 questions on LeetCode by the start date. Some of them have locks, so we will finish all the questions without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.