Force deduction - question 561 - array splitting I - step by step parsing

Given length is 2n Array of integers for nums , Your task is to divide these numbers into n Yes , for example (a1, b1), (a2, b2), …, (an, bn) , Make from 1 To n Of min(ai, bi) The sum is the greatest .

---

• Their thinking ：
  It is important to read the questions first , Suppose the length of the given array is 6, Can be divided into 3 Group .
  Suppose we sort first , After sorting, we take two by two ,
  give ：[1,2,3,4]
  Divided into ：(1,2),(3,4)
  min(1,2) = 1
  min(3,4) = 3
  Last , The maximum sum is 4

---

Code 1 ：
A common way of writing in various languages is as follows , use Python As an example ：

class Solution(object):
    def arrayPairSum(self, nums):
        nums.sort()
        res = 0
        for i in range(0, len(nums), 2):
            res += min(nums[i], nums[i + 1])
        return res

---- Time complexity ：O(N * log(N))O(N∗log(N)), More than the 31% Submission of .
---- Spatial complexity ：O(1)O(1).

---

Code 2 ：
about Python for , We can use slicing , Simplify the code to ：

class Solution(object):
    def arrayPairSum(self, nums):
        nums.sort()
        return sum(nums[::2])

---- Time complexity ：O(N * log(N))O(N∗log(N)), More than the 100% Submission of , Visible slice ratio for The cycle is faster .
---- Spatial complexity ：O(N)O(N), Slicing produces a new array , It takes up space .

---

Code three ：
about Python for , Code 2 above can be further reduced to one line . because nums.sort() It's in place 、 no return value , So we need to use sorted(nums) Function returns a new array , We can continue slicing on the basis of the returned results .

class Solution(object):
    def arrayPairSum(self, nums):
        return sum(sorted(nums)[::2])

---- Time complexity ：O(N * log(N)), Slower than method 2 . Should be sorted() Function copies the array, resulting in .
---- Spatial complexity ：O(N),sorted() Functions and slicing operations produce new arrays , It takes up space .

---

Code example ：

class Solution:
    def arrayPairSum(self, nums) -> int:
        nums.sort()  #  Sort 
        print(' After sorting nums：',nums)
        result = 0
        for i in range(0, len(nums), 2):  #  Every interval 2 A unit of , Add a value 
            print('i:',i)
            print('nums[i]',nums[i])
            print(' primary result:', result)
            result += nums[i]
            print('result:', result)
        return result

#  Given length is 2n Array of integers for nums , Your task is to divide these numbers into n  Yes ,  for example  (a1, b1), (a2, b2), ..., (an, bn) , Make from  1  To n  Of  min(ai, bi)  The sum is the greatest .
#  Return to the   Maximum sum  .
#  The length is 6, It can be divided into 3 Group .
#  Input ：nums = [1,4,3,2]
#  Output ：4
#  explain ： All possible divisions （ Ignore element order ） by ：
# 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  4


if __name__ == '__main__':
    s = Solution()
    nums = [6,2,6,5,1,2]
    result_list = s.arrayPairSum(nums)
    print('result_list:', result_list)

Output is ：

 After sorting nums： [1, 2, 2, 5, 6, 6]
i: 0
nums[i] 1
 primary result: 0
result: 1

i: 2
nums[i] 2
 primary result: 1
result: 3

i: 4
nums[i] 6
 primary result: 3

result: 9

result_list: 9

Be careful ： I think the code 1 appropriate , The latter is written according to the law .