This article is participating in Python Theme Month. See the link for details

Topic describes

This is 1818 on LeetCode. Absolute difference sum, medium difficulty.

Tag: “Dichotomy”

You are given two positive integer arrays nums1 and nums2, both of length N.

The absolute difference between the array nums1 and nums2 and defined as all | nums1 [I] – nums2 [I] | (0 < = I < n) the sum of (subscript starting from 0).

You can replace at most one element of nums1 with any element of nums1 to minimize the absolute sum.

After replacing at most one element in the array nums1, returns the sum of the minimum absolute differences. Because the answer may be large, you need to mod 109+710^9 + 7109+7 and return.

| | x is defined as:

  • If x is greater than or equal to 0, the value is x, or
  • If x <= 0, the value is -x

Example 1:

Input: nums1 = [1,7,5], nums2 = [2,3,5] output: 3 explanation: there are two possible optimal solutions: - replace the second element with the first element: [1,7,5] => [1,1,5], or - replace the second element with the third element: ,5,5,7,5 [1] = > [1] the absolute difference between the two plans and are | 1-2 | + (| | or 1-3 | | 5-3) + | | 5-5 = 3Copy the code

Example 2:

Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10] output: 0 The absolute difference sum is 0Copy the code

Example 3:

Input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4] output: 20 ,10,4,4,2,7,10,4,4,2,7 [1] = > [10] and absolute difference value for 10-9 + | | | 3 | + 10 - | 4-5 + | | | | 4-1 + 2-7 + | | | 7-4 = 20Copy the code

Tip:

  • n == nums1.length
  • n == nums2.length
  • 1 <= n <=
    1 0 5 10^5
  • 1 <= nums1[i], nums2[i] <=
    1 0 5 10^5

binary

This is a dichotomy question, the specific approach is as follows:

Before processing, we copy and sort nums1nums1nums1 to obtain the sortedsortedsorted array.

Then, when traversing nums1nums1nums1 and nums2nums2nums2 to calculate the total difference sumsumsum, perform binary search on sortedsortedsorted. Find the best value to replace nums[I]nums[I].

Specifically, when we deal with the third bit, assume that the original difference of the bit is x=abs(nums1[I]− NUMs2 [I])x=abs(nums1[I] – nums2[I])x=abs(nums1[I]− NUMs2 [I]), Then find the value closest to nums2[I]nums2[I]nums2[I]nums2[I] from the sortedsortedsorted array by binary, calculate a new difference value NDNDND (pay attention to check the segmentation point and the next digit of the segmentation point), If nd< XND < XND

When the entire array is processed, maxmaxmax stores the difference between the optimal solution, and sum−maxsum – maxsum− Max is the answer.

Java code:

class Solution {
    int mod = (int)1e9+7;
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] sorted = nums1.clone();
        Arrays.sort(sorted);
        long sum = 0, max = 0;
        for (int i = 0; i < n; i++) {
            int a = nums1[i], b = nums2[i];
            if (a == b) continue;
            int x = Math.abs(a - b);
            sum += x;
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (sorted[mid] <= b) l = mid;
                else r = mid - 1;
            }
            int nd = Math.abs(sorted[r] - b);
            if (r + 1 < n) nd = Math.min(nd, Math.abs(sorted[r + 1] - b));
            if (nd < x) max = Math.max(max, x - nd);
        }
        return (int)((sum - max) % mod); }}Copy the code

Python 3 code:

class Solution:
    mod = 10支那9 + 7
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) - >int:
        n = len(nums1)
        sortedNums1 = sorted(nums1)
        totalSum = maxDiff = 0
        for i in range(n):
            a, b = nums1[i], nums2[i]
            if a == b:
                continue
            x = abs(a - b)
            totalSum += x
            l, r = 0, n - 1
            while l < r:
                mid = l + r + 1 >> 1
                if sortedNums1[mid] <= b:
                    l = mid
                else:
                    r = mid - 1
            nd = abs(sortedNums1[r] - b)
            if r < n - 1:
                nd = min(nd, abs(sortedNums1[r + 1] - b))
            if nd < x:
                maxDiff = max(maxDiff, x - nd)
        return (totalSum - maxDiff) % self.mod
Copy the code
  • Time complexity: YessortedThe complexity of copying and sorting is
    O ( n log ⁡ n ) O(n\log{n})     ; When iterating through the array, we will try to find the most suitable replacement value while counting, and the complexity is
    O ( n log ⁡ n ) O(n\log{n})     . The overall complexity is
    O ( n log ⁡ n ) O(n\log{n})
  • Space complexity: UsesortedAn array of need
    O ( n ) O(n)     The spatial complexity, while sorting process will be used
    O ( log ⁡ n ) O(\log{n})     Spatial complexity; The overall complexity is
    O ( n + log ⁡ n ) O(n + \log{n})

The last

This is the No.1818 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have 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.