Leetcode -1818- Absolute difference sum

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

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) (subscript from0Start). 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 could be big, it needs to be right109 + 7Return after mod. | | x is defined as: if x > =0, the value is x, or if x <=0For example, the value is -x1: Input: nums1 = [1.7.5], nums2 = [2.3.5] output:3Explanation: There are two possible optimal solutions: - Replace the second element with the first: [1.7.5] = > [1.1.5], or - replace the second element with the third: [1.7.5] = > [1.5.5] the absolute difference between the two plans and are |1-2(| | +1-3Or | |5-3+ | |)5-5| = 3The sample2: Input: nums1 = [2.4.6.8.10], nums2 = [2.4.6.8.10] output:0Explanation: nums1 is equal to nums2, so there is no element replacement. The sum of absolute differences is0The sample3: Input: nums1 = [1.10.4.4.2.7], nums2 = [9.3.5.1.7.4] output:20Explanation: Replace the first element with the second: [1.10.4.4.2.7] = > [10.10.4.4.2.7] for | and absolute difference10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20N == nums1.length n == nums2.length1 <= n <= 105 
 1 <= nums1[i], nums2[i] <= 105Related Topics Greedy array binary find ordered collection 👍52 👎 0
Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Violence

  • Find the absolute value of the difference for each element
  • Change after the difference between absolute minimum * * | nums1 [I] – nums2 [I] | – | nums1 [j] – nums2 [I] | * * biggest, to guarantee the difference and minimum after the change
  • The size of the first half varies according to I and is a constant value. The smaller the second half, the greater the difference
  • So you can look for the element in nums1 that is closest to nums2[I]
  • The TLE
public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
            int sum = 0, index = 0, mod = (int) 1e9 + 7;
            int[] cal = new int[nums1.length];
            for (int i = 0; i < nums1.length; i++) {
                int temp = Math.abs(nums1[i] - nums2[i]);
                cal[i] = temp;
                sum = Integer.MAX_VALUE - sum < temp ? sum % mod + temp : sum + temp;
            }
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < nums1.length; i++) {
                for (int num1 : nums1) {
                    max = Math.max(cal[i] - Math.abs(num1 - nums2[i]), max);
                     if (num1 == nums2[i]){
                        break; }}}return (sum + mod - max) % mod;
        } end.add(0);
            res.add(end);
            return res;
        }
Copy the code


Time complexity O ( n 2 ) Time complexity O(n^{2})

Idea two: idea one optimization – binary search

  • The first idea is to compare each element of NUMs1 to find the minimum value
  • You can sort NUMs1 and then do a binary lookup
  • The time complexity ranges from n2−> 2Lgnn ^{2} -> 2lg_{n}n2−>2lgn
public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
            int sum = 0, mod = (int) 1e9 + 7;
            int[] cal = new int[nums1.length];
            for (int i = 0; i < nums1.length; i++) {
                int temp = Math.abs(nums1[i] - nums2[i]);
                cal[i] = temp;
                sum = Integer.MAX_VALUE - sum < temp ? sum % mod + temp : sum + temp;
            }
            Arrays.sort(nums1);
            int max = 0;
            for (int i = 0; i < nums1.length; i++) {
                if (cal[i] == 0) {continue;
                }
                int index = binarySearch(nums1, nums2[i]);
                int dis = Math.abs(nums1[index] - nums2[i]);
                // Determine if the current index is the closest value, or if the element next to I is the closest value
                if (index + 1 < nums1.length) {
                    dis = Math.min(dis, Math.abs(nums1[index + 1] - nums2[i]));
                }
                / / confirm | nums1 [I] - nums2 [I] | - | nums1 [j] - nums2 [I] | is the largest
                max = Math.max(cal[i] - dis,max );
            }
            // Ensure that -max does not have negative numbers
            return (sum + mod - max) % mod;
        }

        /** * Find an element with the current position <= target and the next element empty or greater than target **@param nums
         * @param target
         *
         * @return* /
        public int binarySearch(int[] nums, int target) {
            int l = 0, r = nums.length - 1, mid = (l - r) / 2 + r;
            //corner
            if (nums[r] < target) {
                return r;
            }
            while (l < r) {
                mid = (l - r) / 2 + r;
                if (nums[mid] == target) {
                    return mid;
                }
                if (nums[mid] > target) {
                    r = mid - 1;
                } else{ l = mid; }}returnr; }}Copy the code


Time complexity O ( n ∗ l g n ) Time complexity O(n*lg_{n})