0561. Array Partition I

561. Array Partition I #

题目 #

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:

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

题目大意 #

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。

解题思路 #

  • 给定一个 2n 个数组,要求把它们分为 n 组一行,求出各组最小值的总和的最大值。
  • 由于题目给的数据范围不大,[-10000, 10000],所以我们可以考虑用一个哈希表数组,里面存储 i - 10000 元素的频次,偏移量是 10000。这个哈希表能按递增的顺序访问数组,这样可以减少排序的耗时。题目要求求出分组以后求和的最大值,那么所有偏小的元素尽量都安排在一组里面,这样取 min 以后,对最大和影响不大。例如,(1 , 1) 这样安排在一起,min 以后就是 1 。但是如果把相差很大的两个元素安排到一起,那么较大的那个元素就“牺牲”了。例如,(1 , 10000),取 min 以后就是 1,于是 10000 就“牺牲”了。所以需要优先考虑较小值。
  • 较小值出现的频次可能是奇数也可能是偶数。如果是偶数,那比较简单,把它们俩俩安排在一起就可以了。如果是奇数,那么它会落单一次,落单的那个需要和距离它最近的一个元素进行配对,这样对最终的和影响最小。较小值如果是奇数,那么就会影响后面元素的选择,后面元素如果是偶数,由于需要一个元素和前面的较小值配对,所以它剩下的又是奇数个。这个影响会依次传递到后面。所以用一个 flag 标记,如果当前集合中有剩余元素将被再次考虑,则此标志设置为 1。在从下一组中选择元素时,会考虑已考虑的相同额外元素。
  • 最后扫描过程中动态的维护 sum 值就可以了。

代码 #


package leetcode

func arrayPairSum(nums []int) int {
	array := [20001]int{}
	for i := 0; i < len(nums); i++ {
		array[nums[i]+10000]++
	}
	flag, sum := true, 0
	for i := 0; i < len(array); i++ {
		for array[i] > 0 {
			if flag {
				sum = sum + i - 10000
			}
			flag = !flag
			array[i]--
		}
	}
	return sum
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者