Leetcode基础刷题之PHP解析(268. Missing Number)


2019-4-18 期四  

 Leetcode基础刷题之PHP解析(263. Ugly Number)

13b8f6a29c7f9df0a812e65fa5b9e697.png

查找缺失的数。给你一组数组,查找从0-n中缺少的整数。有点坑爹的是如果给你的是[0,1,2],为了返回回来的都是有缺失的数,所以这里应该返回3。

解法很多。第一种就是迭代他哪个位置空缺返回哪个数,如果都没有返回数组最后一个数加1。

解法二

使用二分查找,每次获取中间元素的下标和下标对应的值进行比较,如果下标对应的值大于元素下标,说明缺失的数字在右边,把右边赋值给中间下标,否则左边就来到中间下标的下一个位置。


解法三

可能你已经发现了, 以上两个操作都先把数组进行排序,那么在效率上就....,所以还能不能有其他解法,异或。因为0-n之间缺少一个数,我们只要把完整的数组和缺少1个的数组异或一下,相同的都变成0,多出来的当然就是缺少的哪个数。

Github整理地址:https://github.com/wuqinqiang/leetcode-php



<< 上一篇: Leetcode基础刷题之PHP解析(263. Ugly Number)

>> 下一篇: Leetcode PHP题解--D35 876. Middle of the Linked List