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

Topic describes

This is 561 on LeetCode. Array split I, easy to do.

Tag: “Greedy algorithms”

Given an array of integers of length 2N, nums, your task is to divide the numbers into N pairs, such as (A1, b1), (a2, B2),… , (an, bn), maximizing the sum of min(ai, bi) from 1 to n.

Returns the maximum sum.

Example 1:

Input: nums = [1,4,3,2] output: 4 explanation: all possible partitions (ignoring element order) are:  1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3 2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3 3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4, so the maximum sum is 4Copy the code

Example 2:

Input: nums =,2,6,5,1,2 [6] output: 9: an optimal method for (2, 1), (2, 5), (6, 6), min (2, 1) + + min min (2, 5) (6, 6) = 1 + 2 + 6 = 9Copy the code

Tip:

  • 1 <= n <=
    1 0 4 10^4
  • nums.length == 2 * n
  • –
    1 0 4 10^4     <= nums[i] <=
    1 0 4 10^4

Greedy method

Let’s sort the array first.

Because of every two numbers, we can only sum up the current smaller number.

So we guess we should pick the first one, and then pick the next one. The resulting sequence has the maximum sum.

class Solution {
    public int arrayPairSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n; i += 2) ans += nums[i];
        returnans; }}Copy the code
  • O(nlog⁡n)O(n\log{n})O(nlogn)
  • Space complexity: O(log⁡n)O(\log{n})O(logn)

prove

Let’s prove by contradiction why the sum of the selected sequences must be the largest:

Guess: Sort the array, select from the first position, and then select the next number every step. The resulting sequence has the maximum sum (the black bar below represents the currently selected number).

We can do this because the “next position” of each selected number corresponds to a value that is “greater than or equal to” the current number (assuming position k), making the current number selectable in min(a,b) relation (the red bar below represents the auxiliary number that ensures the previous black bar can be selected).

If the sequence sum we chose is not the maximum, then at least one of the values we chose was wrong and we should have chosen a larger number.

So the black bar that means “a certain position” should point from the current position to a later position.

PS. Since the numbers are accumulated only when min(a, b) is satisfied, the right shift of each red label (becoming larger) will inevitably lead to the “same or different degree” right shift of the original corresponding black label (becoming larger).

This will cause all of our red and black markers to shift back at the same time.

So it’s going to result in our last black mark now the last black mark, and then the last black mark has to pair with our number in the KTH position.

Let’s see that this is the change in the summation sequence (the sum before k position does not change, we start from k position) :

  1. The original answer =nums[k] + nums[k + 2] + ... + nums[n - 1]
  2. Adjusted answer =nums[k + 1] + nums[k + 3] + ... + nums[n - 2] + min(nums[n], nums[k])

Since min(nums[n], nums[k]) must be nums[k] selected. = nums[k] + nums[k + 1] + nums[k + 3] + nums[k + 3] +… + nums[n – 2]

Obviously, every term of the original answer is “greater than or equal to” every term of the adjusted answer, so it is impossible to obtain a better solution by choosing other larger numbers in the “hypothetical sequence”, which is supposed to prove.

Why “prove” or “understand proof”?

The point of proof is that you know why it’s right.

The benefits are:

  1. If a “greedy” question can be clearly proved, then you can do all the “greedy” questions of the same kind. Otherwise it’s “I know I can be greedy with this one, I’m not sure I can do the same with the others”.
  2. During the “interview” stage, you can explain your thinking clearly. Get the interviewer to like you for your “way of thinking” (emMM also works for your appearance level)

.

More proof/analysis related questions:

765. Couples holding hands: Why is it right to swap either one? : Two 100% solutions: Look up set & Greedy 1579. Ensure graph is fully traversable: Why is it right to deal with common edges first? Contains greedy proof + array template ~

1631 Path of minimum Physical Exertion: Proof of the legitimacy of the idea by contradiction

11. Container with the most water: Dual pointer + Greedy Solution

The last

This is No.561 of our “Brush through LeetCode” series. The series started on 2021/01/01.

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.