GuoXin Li's Blog

LeetCode561. Array Partition I

LeetCode
字数统计: 268阅读时长: 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
    • Total : 89
    2022
    2021
    2020
    2019
    2018
    essay Deep Learning Paper-reading learning-note C++ CUDA cmake LeetCode DataStructure Numpy OS-Linux PAT slidingwindow git golang BuaaAssignments CG
    Machine-Learning Data-Structure