leetcode 7.20-7.26

2020-07-26

561 数组拆分I
540 有序数字中的单一元素

561. 数组拆分I

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

示例 1:

输入: [1,4,3,2]

输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
提示:

n 是正整数,范围在 [1, 10000].
数组中的元素范围在 [-10000, 10000].

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/array-partition-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：取两个值中的最小值，换个思路想就是会把一个较大的数字屏蔽掉。那么为了让得到的和最大，我希望被屏蔽掉的数字尽可能小=>升序排序，下标为偶数的数字和即为所求。

AC代码：

class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sum(sorted(nums)[::2])

sorted返回排序后的列表；list[start:end_index:step].

C++排序超时就离谱= =

540. 有序数字中的单一元素

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:

输入: [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: [3,3,7,7,10,11,11]
输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：一看到要求log(n)，二分法。结果所在的半边一定是包含奇数个元素的列表。官方题解https://leetcode-cn.com/problems/single-element-in-a-sorted-array/solution/you-xu-shu-zu-zhong-de-dan-yi-yuan-su-by-leetcode/还写了个方法三，有时间仔细研究下（不会有时间的）。

AC代码：

class Solution(object):
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 1:
            return nums[0]
        
        mid = len(nums) / 2
        if nums[mid] == nums[mid+1]:
            if len(nums) == 3:
                return nums[0]
            else:
                mid += 1
        if mid & 0x1 == 0:
            return self.singleNonDuplicate(nums[:mid+1])
        else:
            return self.singleNonDuplicate(nums[mid+1:])