“This is the 22nd day of my participation in the First Challenge 2022. For details: First Challenge 2022”

[B] [C] [D]

Given an array of integers of length 2n ****, nums, your task is to divide these 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 <= 104
  • nums.length == 2 * n
  • -104 <= nums[i] <= 104

Their thinking

Trying to make the sum of the minima of the number pairs as large as possible is the same thing as trying to make the minima of each number pair as large as possible. To make the minimum of two numbers as large as possible, the difference between the two values should be as small as possible, so that the minimum value will be as large as possible. To keep the two values of each numeric pair as small as possible, we can sort the input array in ascending order. After sorting, two adjacent elements form a group of numeric pairs in sequence, which ensures the minimum difference of each numeric pair. Iterate through the sorted array, fetching subscripts 0, 2, 4, 5… The value of the 2n minus 2 element, which is the minimum value of each pair of numbers, you add them up, you walk through the sorted array, and you get the maximum sum.

Code implementation

Var arrayPairSum = function (nums) {nums.sort((a, b) => a - b); The first one is the minimum for (let I = 0; i < nums.length; I += 2) {return nums[I] += nums[I]}Copy the code

At this point we are done with Leetcode-561 – array split I

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻