Make writing a habit together! This is my first day to participate in the “Gold Digging Day New Plan · April More text challenge”, click to see the details of the activity.

Topic describes

This is an array of 954. Diples on LeetCode, of medium difficulty.

Tag: “Priority queue”, “heap”, “Construct”, “hash table”, “topology sort”

Given an integer array arR of even length, only the recombination of arR can satisfy “for each 0<= I

Example 1:

Input: arr = [3,1,3,6Copy the code

Example 2:

Input: arr = [2,1,2,6Copy the code

Example 3:

Input: arr = [4, 2, 2, 4] output: true explanation: can use [2, 4] and [2, 4] the two groups of [2, 4, 4-trichlorobenzene] or [2, 4, 2, 4]Copy the code

Tip:


  • 0 < = a r r . l e n g t h < = 3 ∗ 1 0 4 0 <= arr.length <= 3 * 10^4
  • Arr. The length is even

  • – 1 0 5 < = a r r [ i ] < = 1 0 5 -10^5 <= arr[i] <= 10^5

Construct + priority queues one by one

Can arR be reorganized so that each odd position is twice the value of the previous position, i.e., n2\frac{n}{2}2n pairs of the form (x,2∗x)(x, 2 * x)(x,2∗x) can be formed.

For an arbitrary rational number, multiplying it by 222 only changes its magnitude, not its direction.

So if we take the value closest to 000 as a starting point each time, the entire construction process is uniquely deterministic.

Specifically, we can achieve this with the help of a priority queue (heap), which constructs a small root heap based on the distance from 000 values. Each time the element XXX is fetched from the heap, the case is discussed according to whether the current element XXX is “predetermined” :

  • The current value XXX has not been predetermined, indicating that XXX must be the smaller value of the “absolute value” in the number pair. In this case, XXX is given and a x∗2x * 2x∗2 is predetermined, that is, the predetermined times of X ∗2x * 2x∗2 are added by one.
  • Frac {x}{2}2x = x; frac{x}{2}2x = x; frac{x}{2}2x = x

Arr can form n2\frac{n}{2}2n pairs of the form (x,2∗x)(x, 2 * x)(x,2∗x) if and only if the “predetermined” degree of all numbers is 000 at the end of the construction process.

Some details: As the value range of ARR [I] ARr [I] arR [I] is [−105,105][-10^5, 10^5][−105,105], and multiplication 222 exists at the same time, we need to perform the offset operation of 2∗1052 * 10^52∗105 for the calculated results. Make sure it’s positive.

Code:

class Solution {
    static int N = 100010, M = N * 2;
    static int[] cnts = new int[M * 2];
    public boolean canReorderDoubled(int[] arr) {
        Arrays.fill(cnts, 0);
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->Math.abs(a)-Math.abs(b));
        for (int i : arr) q.add(i);
        while(! q.isEmpty()) {int x = q.poll(), t = x * 2;
            if(cnts[x + M] ! =0 && --cnts[x + M] >= 0) continue;
            cnts[t + M]++;
        }
        for (int i = 0; i < M * 2; i++) {
            if(cnts[i] ! =0) return false;
        }
        return true; }}Copy the code
  • Time complexity: let
    n n     为 arrThe length,
    m m     为
    a r r [ i ] arr[i]     The initial complexity of putting all values into the priority queue (heap) is
    O ( n log ⁡ n ) O(n\log{n})     , is taken from the priority queue (heap) and the construction complexity is
    O ( n log ⁡ n ) O(n\log{n})     , check whether the construction is successful
    O ( m ) O(m)     , the overall complexity is
    O ( n log ⁡ n + m ) O(n\log{n} + m)
  • Space complexity: O(n+m)O(n +m)O(n +m)

Group construction + sorting + preprocessing pruning

In the above solution, it is inevitable to conduct a completed trial construction of ARR, and then conduct a one-time legitimacy check after the trial construction.

In fact, if arR can form n2\frac{n}{2}2n pairs of the form (x,2∗x)(x, 2 * x)(x,2∗x), which may occur multiple times for a given XXX, we can count the number of arr[I]arr[I]arr[I], In order of absolute value, group structure was carried out: CNTS [x] CNTS [x] CNTS [X] [X] XXX consume CNTS [x] CNTS [x] [x] 2∗x2 * x2∗x.

At the same time, since the occurrence times of each ARR [I] arR [I] were preprocessed in advance, we could know whether there were CNTS [x] CNTS [X] [X] 2∗x2 * x2∗x and XXX group in advance, so as to check the legality while constructing.

Code:

class Solution {
    static int N = 100010, M = N * 2;
    static int[] cnts = new int[M * 2];
    public boolean canReorderDoubled(int[] arr) {
        Arrays.fill(cnts, 0);
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            if (++cnts[i + M] == 1) list.add(i);
        }
        Collections.sort(list, (a,b)->Math.abs(a)-Math.abs(b));
        for (int i : list) {
            if (cnts[i * 2 + M] < cnts[i + M]) return false;
            cnts[i * 2 + M] -= cnts[i + M];
        }
        return true; }}Copy the code
  • Time complexity: Count the occurrence times of ARr [I]arr[I]arr[I] and the complexity of deduplication for ARr [I]arr[I] is O(n)O(n)O(n) O(n\log{n})O(nlogn), The verification complexity is O(n)O(n)O(n). The overall complexity is O(nlog⁡n)O(n\log{n})O(nlogn)
  • Space complexity: O(n+m)O(n +m)O(n +m)

Group construction + topological sort

In both cases, either a “priority queue” or a “sort” is used in order to find the “lower absolute value” digit in the pair and start building backwards.

In fact, we can use any of these
x x Only possible with
x 2 \frac{x}{2} or
2 ∗ x 2 * x Form a number pair to build the graph, and run the topology sequence to verify whether the graph can be completed
n 2 \frac{n}{2} Groups like
( x . 2 ∗ x ) (x, 2 * x) The number of pairs.

For those who are not familiar with topological sorting, see 🧀 : Introduction to topological sorting in graph theory, which illustrates what topological ordering is and why directed acyclic graphs are capable of topological sorting through “proof by contradiction”.

In particular, we need to handle the case where arr[I]= 0ARr [I]=0arr[I]=0. Since 000 can only be paired with itself, we need to skip the point where arr[I]=0arr[I]=0arr[I]=0 to avoid self-loop. At the same time, if the occurrence number of arr[I]= 0ARr [I]=0arr[I]=0 is odd, no solution is returned.

Arr [I]arr[I]arr[I]arr[I]arr[I]arr[I]arr[I]arr[I]arr[I] (skip 000)

  • * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  • In [x]= CNTS [x2]in[x] = CNTS [\frac{x}{2}]in[x]= CNTS [2x], There are CNTS [x2] CNTS [frac{x}{2}] CNTS [2x] x2 {x}{2}2x corresponding to them. If in[x]=0in[x] =0in[x] =0, x2\frac{x}{2}2x is not paired with x2\frac{x}{2}2x. In [x]=0in[x] =0, x2\frac{x}{2}2x is not paired with x2\frac{x}{2}2x.

Run the topology sort, assuming that the current queue value is TTT, At this point, the t∗ 2T * 2T ∗2 of CNTS [T] CNTS [T] [T] CNTS [T ∗2]−= CNTS [T] CNTS [T * 2] -= CNTS [T] CNTS [T ∗2]−= CNTS [T] ∗2]−= CNTS [T] At the same time, the input of T ∗2t * 2T ∗2 should also be updated (i.e., in[T ∗2]−= CNTS [t]in[T * 2] -= CNTS [t]in[T ∗2]−= CNTS [T]). If in[T ∗2]=0in[T * 2]=0in[T ∗2]=0 and CNTS [T ∗2]>0cnts[T * 2]>0cnts[T ∗2]>0, T ∗2t * 2T ∗2 is recruited. Meanwhile, as the number of T ∗2t * 2t∗2 is clearly reduced, the input of T ∗4t * 4t∗4 needs to be updated synchronically. Similarly, when the input of T ∗4t * 4t∗4 is in[T ∗4]=0in[t * 4]=0in[T ∗4]=0, At the same time, when CNTS [T ∗4]>0cnts[T * 4]>0cnts[T ∗4]>0, T ∗4t * 4T ∗4 needs to be recruited.

Code:

class Solution {
    static int N = 100010, M = 2 * N;
    static int[] cnts = new int[M * 2], in = new int[M * 2];
    public boolean canReorderDoubled(int[] arr) {
        Arrays.fill(cnts, 0);
        Arrays.fill(in, 0);
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            if (++cnts[i + M] == 1&& i ! =0) list.add(i);
        }
        if (cnts[0] % 2! =0) return false;
        Deque<Integer> d = new ArrayDeque<>();
        for (int i : list) {
            if (i % 2= =0) {
                in[i + M] = cnts[i / 2 + M];
                if (in[i + M] == 0) d.addLast(i);
            } else{ d.addLast(i); }}while(! d.isEmpty()) {int t = d.pollFirst();
            if (cnts[t * 2 + M] < cnts[t + M]) return false;
            cnts[t * 2 + M] -= cnts[t + M];
            in[t * 2 + M] -= cnts[t + M];
            if (in[t * 2 + M] == 0 && cnts[t * 2+ M] ! =0) d.addLast(t * 2);
            in[t * 4 + M] -= cnts[t + M];
            if (in[t * 4 + M] == 0 && cnts[t * 4+ M] ! =0) d.addLast(t * 4);
        }
        return true; }}Copy the code
  • Time complexity: The complexity of statistics quantity and input degree is O(n)O(n)O(n). The complexity of running topology sequence verification is O(n)O(n)O(n). The overall complexity is O(n)O(n)O(n)
  • Space complexity: O(n+m)O(n +m)O(n +m)

reading

Introduction to graph topological sorting: Illustrates what topological ordering is and proves why topological ordering can be done by directed acyclic graphs 🎉 🎉

The last

This is the No.954 article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks, so we will finish all the topics without locks.

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.