LeetCode撸代码之：561. Array Partition I

答案：

1import java.util.Arrays;
2
3class Solution {
4    public int arrayPairSum(int[] nums) {
5
6        selectSort(nums);
7        int len = nums.length;
8        int sum = 0;
9        for (int i = 0; i < len; i += 2) {
10            sum += nums[i];
11        }
12        return sum;
13    }
14
15
16    public void selectSort(int[] num) {
17
18        for (int i = 0, size = num.length; i < size; i++) {
19            int minIndex = i;
20            for (int j = i; j < num.length; j++) {
21                if (num[j] < num[minIndex]) {
22                    minIndex = j;
23                }
24            }
25
26            swap(num, minIndex, i);
27
28        }
29
30
31    }
32
33    private void swap(int[] num, int index1, int index2) {
34        int tmp = num[index1];
35        num[index1] = num[index2];
36        num[index2] = tmp;
37
38    }
39
40    /**
41     * @param num   待排序数组
42     * @param start 数组起始index
43     * @param end   数组结束的index
44     * @return 返回provit位置
45     */
46    private int partition(int[] num, int start, int end) {
47        int pivot = num[start];
48
49        while (start < end) {
50            while (start < end && num[end] >= pivot)
51                end--;
52            swap(num, start, end);
53
54            while (start < end && num[start] <= pivot)
55                start++;
56            swap(num, start, end);
57
58        }
59
60        num[start] = pivot;
61
62        return start;
63
64    }
65
66    private void sort(int[] num, int start, int end) {
67        if (start >= end) {
68            return;
69        }
70        int mid = partition(num, start, end);
71        sort(num, start, mid - 1);
72        sort(num, mid + 1, end);
73    }
74
75
76    public static void main(String[] args) {
77        int[] num = new int[]{7,3,1,0,0,6};
78        new Solution().selectSort(num);
79
80        System.out.println(Arrays.toString(num));
81    }
82
83}

这道题目本质就是考察排序算法，为了让结果最大，只有大数跟大数分组在一起的话，组内次大数才会被选出来求和。所以需要对数组排序，可以使用JDK算法或者自己实现排序算法。本人尝试快排可以AC，但是选择由于复杂度会超时。