淘宝上 网站建设爱站小工具

268. 丢失的数字

LC将此题归类为二分查找，并且为简单题，下面记一下自己对这道题目的思考。
题目链接：268.丢失的数字


第一次看到这个题目，虽然标注的为简单，但肯定不能直接排序或者使用哈希表去实现，如果这样做的话这道题目就没有任何意义。我首先联想到一道剑指offer上面的一道原地哈希的题目，但具体写的时候下笔难。
下面参考宫水三叶的题解，自己重新写一遍。
方法一：原地哈希：
由于题目所述为查找nums[]一共n个数，[0, n]这n + 1个数哪个不存在与数组中。借助nums本体数组，使用原地哈希，每次碰到一个数字，如果不符合nums[i] == i，此时将nums[i]移动到对应numsp[i]的位置上，继续从i开始遍历。
第一遍遍历完成后，再此遍历nums数组，如果碰到nums[i] != i 此时直接返回 i ，否则遍历完毕仍然没有遇到符合要求的数，此时直接返回n。
代码如下所示：

class Solution {public int missingNumber(int[] nums) {// 原地交换int n = nums.length;for(int i = 0; i < n; i++){if(nums[i] != i && nums[i] < n){// 这里为什么要i--，因为这个交换操作只是将nums[i]对应的元素移到了它应该处于的位置nums[i]上，//但原本nums[i]位置的数组却被交换到i位置了，下次遍历需要继续从i位置开始遍历，由于for循环中对i不断++所以这里需要进行-1操作。swap(nums, nums[i], i--);}}for(int i = 0; i < n; i++){if(nums[i] != i){return i;}}return n;}public void swap(int[] nums, int i, int j){int num = nums[i];nums[i] = nums[j];nums[j] = num;}
}

方法二：异或操作：
如果做过：【只有一个数字出现1次，其他数字都出现两次】这个题目，相信也可以对题目稍加改造，将其构造为这个题目，具体操作，首先将ans 异或[0, n]随后，遍历nums数组并对ans进行异或操作。这样处理后，最终的ans就是返回答案。

class Solution {public int missingNumber(int[] nums) {//异或int ans = 0, n = nums.length;for(int i = 0; i <= n; i++){ans ^= i;}for(int i = 0; i < n; i++){ans ^= nums[i];}return ans;}
}

方法三：等差数组求和：
由于题目所述为寻找[0, n] 这n + 1个数字在nums中没有出现的数字，先对[0, n]这n + 1个数字使用等差数列求和，计为sum。再遍历nums，对nums中所有数组求和curSum，随后sum - curSum即为最终答案。

代码：

class Solution {public int missingNumber(int[] nums) {int n = nums.length;int curSum = 0, sum = n * (n + 1) / 2;for(int num : nums){curSum += num;}return sum - curSum;}}

162. 寻找峰值

题目链接：162.寻找峰值

这个题目散发出熟悉的味道，之前做过，并且也成功做出来了，但是这次没看题解代码写的比别人题解非常负责，具体可以参考后面写的代码示例。
基本思想：使用二分查找思想，[l, r] 求的mid后，比较nums[mid] 和 nums[mid + 1]的大小关系。（为什么比较nums[mid] 和 nums[mid + 1]而不是比较nums[mid] 和 nums[mid - 1]的大小：Java中向下取整的，保证有两个数的前提下，通过(l + r) / 2 计算出的mid，此时mid + 1一定不会越界的，相反对于mid - 1可能会越界，在只有两个数的情况下就会越界。）
随后根据nums[mid] 和 nums[mid + 1]的大小关系移动左右边界。

1. nums[mid] > nums[mid + 1] 此时，mid可以用，并且由于左边数更大，所以边界向左边收缩。r = mid。
2. 不满足1，此时mid 是不可用的，此时向右边界收缩，r = mid + 1。

上面思路的前提，nums[-1] == nums[n] = -00。

代码展示：

class Solution {public int findPeakElement(int[] nums) {int len = nums.length;if(len == 1)    return 0;int l = 0, r = len - 1;while(l < r){int mid = l + (r - l) / 2;if((mid == 0 && nums[mid] > nums[mid + 1]) || (mid == len - 1 && nums[mid] > nums[mid - 1])){return mid;}if(mid > 0 && mid < len - 1 && nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]){return mid;}if(nums[mid] > nums[mid + 1]){r = mid - 1;}else{l = mid + 1;}}return l;}
}// 之前参考题解的代码：
class Solution {public int findPeakElement(int[] nums) {int left = 0, right = nums.length - 1;while(left < right){int mid = (left + right) / 2;if(nums[mid] > nums[mid + 1]){right = mid;}else{left = mid + 1;}}return left;}
}