答案:
import java.util.Arrays;
class Solution {
public int arrayPairSum(int[] nums) {
selectSort(nums);
int len = nums.length;
int sum = 0;
for (int i = 0; i < len; i += 2) {
sum += nums[i];
}
return sum;
}
public void selectSort(int[] num) {
for (int i = 0, size = num.length; i < size; i++) {
int minIndex = i;
for (int j = i; j < num.length; j++) {
if (num[j] < num[minIndex]) {
minIndex = j;
}
}
swap(num, minIndex, i);
}
}
private void swap(int[] num, int index1, int index2) {
int tmp = num[index1];
num[index1] = num[index2];
num[index2] = tmp;
}
/**
* @param num 待排序数组
* @param start 数组起始index
* @param end 数组结束的index
* @return 返回provit位置
*/
private int partition(int[] num, int start, int end) {
int pivot = num[start];
while (start < end) {
while (start < end && num[end] >= pivot)
end--;
swap(num, start, end);
while (start < end && num[start] <= pivot)
start++;
swap(num, start, end);
}
num[start] = pivot;
return start;
}
private void sort(int[] num, int start, int end) {
if (start >= end) {
return;
}
int mid = partition(num, start, end);
sort(num, start, mid - 1);
sort(num, mid + 1, end);
}
public static void main(String[] args) {
int[] num = new int[]{7,3,1,0,0,6};
new Solution().selectSort(num);
System.out.println(Arrays.toString(num));
}
}
这道题目本质就是考察排序算法,为了让结果最大,只有大数跟大数分组在一起的话,组内次大数才会被选出来求和。所以需要对数组排序,可以使用JDK算法或者自己实现排序算法。本人尝试快排可以AC,但是选择由于复杂度会超时。