1 Description
561. Array Splitting I - LeetCode ()
The given length is2nInteger Arraynums, your task is to divide these numbers intonFor example, (a1, b1), (a2, b2), ..., (an, bn) , such that the sum of min(ai, bi) from 1 to n is the largest.
Returns the maximum sum.
Example 1:
enter：nums = [1,4,3,2] Output：4 explain：All possible divisions（Ignore the order of elements）for： 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 所以最大总和for 4
Example 2:
enter：nums = [6,2,6,5,1,2] Output：9 explain：The optimal classification is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9
hint:
1 <= n <= 10^4
== 2 * n
-10^4 <= nums[i] <= 10^4
Two Analysis
The essential idea is to sort the entire queue from small to large, and then select the smallest from two similar numbers and take the sum. Using the bubble method will exceed the calculation time because you choose to add an additional array and use the size as the lower corner of the two arrays to sort it.
Three Answers
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
/*
int arr[()]={0};
int temp=0;
for(int i=0;i<();i++)
arr[i]=nums[i];
for(int i=0;i<()-1;i++)
{
for(int j=i+1;j<();j++)
if(arr[i]>arr[j]) {temp=arr[i];arr[i]=arr[j];arr[j]=temp;} //The bubbling sort will exceed the time limit
}
int res=0;
for(int i=0;i<();i+=2){res+=arr[i];}
return res;*/
int n[20001]={0},i=0,j=0,sum=0;
for(i=0;i<();i++)
n[nums[i]+10000]++; //Or sort nums in disguise in size and store the order in n[i] for(i=0;i<20001;)
{
if(n[i])
{
if(j%2==0) sum+=i-10000; //Follow nums[i] in the order stored in n[i], find nums[i] j++; //J will only increase when there is a number in n[i], that is, when nums exists, j will increase and change j to the lower corner mark n[i]--; //This step prevents nums from containing two identical numbers }
else i++;
}
return sum;
}
};
Python Language - Array Splitting
Problem-solving ideas
Sort
Today's question means: split the input array into nn pairs, sum the minimum value of each pair, and get the maximum result.
Start with the examples given in the question:
For example two [6,2,6,5,1,2]:
The optimal score given by the question is (2, 1), (2, 5), (6, 6), min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.
If we change the classification method: (2, 6), (2, 5), (1, 6), min(2, 6) + min(2, 5) + min(1, 6) = 2 + 2 + 1 = 5, the final result will be smaller.
It can be seen that small numbers form a pair and large numbers form a pair. After each pair takes minmin, the result obtained by summing is the largest.
Therefore, the idea is to sort the input array numsnums, and then find the minimum value of two adjacent elements in sequence, and the sum is the result.
Code 1
A common writing method for various languages is as follows, using Python as an example:
class Solution(object):
def arrayPairSum(self, nums):
()
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)), exceeding 31% of submissions.
Space complexity: O(1).
Code Two
For Python, we can use slice operations to simplify the code to:
class Solution(object):
def arrayPairSum(self, nums):
()
return sum(nums[::2])
Time complexity: O(N * log(N)), exceeding 100% of the submissions, visible slices are faster than for loops.
Space complexity: O(N), slice operation produces a new array, taking up space.
Code Three
For Python, the above code 2 can continue to be reduced to one line. Since () is operated in place and has no return value, we need to use the sorted(nums) function to return a new array so that we can continue to slice based on the result returned.
class Solution(object):
def arrayPairSum(self, nums):
return sum(sorted(nums)[::2])
Time complexity: O(N * log(N)), exceeding 63% of the submissions, which is slower than method two. It should be caused by the sorted() function copying the array.
Space complexity: O(N), sorted() functions and slice operations produce new arrays, taking up space.
Experience in writing questions
Easy questions often start with examples and analyze solutions.
This question practices slicing operations in Python and also practices writing two sorting functions.
The above is the detailed content of the LeetCode561 array splitting solution for Go language problems. For more information about Go language array splitting, please pay attention to my other related articles!