Lipsky

LeetCode561. Array Partition I

字数统计: 270阅读时长: 1 min
2020/02/24 Share

561. Array Partition I#

LeetCode 561

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:

n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

1
2
3
4
5
6
7
8
9
10
11
//java
class Solution {
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length; i+=2){
sum += nums[i];
}
return sum;
}
}

Time Complexity: $O(nlogn)$

Space Complexity: $O(1)$

note: Arrays.sort algrithm

Bucket Sort#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public int arrayPairSum(int[] nums) {
// Arrays.sort(nums);
// int sum = 0;
// for (int i = 0; i < nums.length; i+=2){
// sum += nums[i];
// }
// return sum;
int[] n = new int[20001];
int sum = 0;
for (int i = 0; i < nums.length; i++){
n[nums[i]+10000]++;
}
int index = 0;
for (int i = 0; i < n.length; ){
if(n[i]!=0){ //judge n[i] exists number
if(index % 2 == 0){ //judge index is even
sum += (i-10000);
}
n[i]--; //spend a time
index++; //numbers of existed number add
}else{
i++; //n[i] doesn't exitst. i-->
}
}
return sum;
}
}
CATALOG
  1. 1. 561. Array Partition I#
  • Bucket Sort#