vlambda博客
学习文章列表

披星戴月奔向理想和你

你好呀 

我是苏钟白

题目来源|Leetcode官网

9

剑指 Offer 53 - II. 0～n-1中缺失的数字

题目：

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]

输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9]

输出: 8

思路：

最容易想到的是0-n遍历，判断i是否在数组里，不在则返回i，跑了1280ms。其次可以想到对于这样的一个递增数组，下标与数是一致的，如果index与数不一样，则说明这个数缺失。另一个方法就是二分查找法。

那什么是二分查找法呢？

（提问：什么是快速排序法？什么是摩尔投票法？）

对于有序数组，找数组的中间数与目标查找数比较，如果找到则结束，如果中间数大于目标数，则在中间数前半部分循环这个过程，如中间数小于目标数则在中间数后半部分循环这个过程，直到找到目标数，否则数组中没有该数。

如何用二分查找解决这题？

我们先设置两个左右指针，一头一尾，然后不断的判断两个指针的中间mid与该中间数索引对应的元素nums[mid]是否相等，相等则说明中间索引左边的所有元素都是有的，缺失的数在右边，所以左边的指针等于mid+1，否则右边的指针等于mid-1。最后返回的左指针就是缺失的值。具体可看下面的代码。

代码：

9

888. 公平的糖果交换

题目：

爱丽丝和鲍勃拥有不同总数量的糖果。有两个数组 aliceSizes 和 bobSizes ，aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量，bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。

两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。

返回一个整数数组 answer，其中 answer[0] 是爱丽丝必须交换的糖果盒中的糖果的数目，answer[1] 是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中 任何一个 。题目测试用例保证存在与输入对应的答案。

示例 1：

输入：aliceSizes = [1,1], bobSizes = [2,2]输出：[1,2]

示例 2：

输入：aliceSizes = [1,2], bobSizes = [2,3]输出：[1,2]

示例 3：

输入：aliceSizes = [2], bobSizes = [1,3]输出：[2,3]

示例 4：

输入：aliceSizes = [1,2,5], bobSizes = [2,4]输出：[5,4]

思路：

看到题目想到的思路是两层for循环，交换alice的元素和bob中每个元素，如果交换后两个数组和相等则返回结果，否则再把两个数交换回来。但果不其然，超时。

这题主要想到差值gap，即用alice数组的和减去bob数组的和再除以2。然后对于alice中的元素，只需在bob中判断有没有该元素-gap。

想到三种方法，一种就是直接判断，一种是先排序然后二分查找，一种是双指针。

这里简单说一下二分查找法。

就是对bob排序，对alice中的元素循环，对左右两个指针求中间值mid，如果循环到的元素bob[mid]大于k-gap,说明k-gap在bob[mid]左边，右指针等于mid-1。具体可看代码。

代码：