作者:whisper
链接:https://www.proprogrammar.com/article/878
声明:请尊重原作者的劳动,如需转载请注明出处
一个长度为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
难度:简单;标签:数组,二分查找;编程语言:JAVA
class Solution {
public int missingNumber(int[] nums) {
int sum = 0;
for(int n: nums)sum += n;
return -sum + (nums.length + 1) * nums.length / 2;
}
}
不缺数时是等差数列,可以等差数列求和,缺时和也算出来,减一下
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] != i) return i;
}
return n;
}
}
这里利用数组是递增的来做的
class Solution {
public int missingNumber(int[] nums) {
int i = 0, j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] == m) i = m + 1;
else j = m - 1;
}
return i;
}
}
这里是利用二分法来做的,nums[m] == m时,是正常的,缺的数在右边,不正常时在左边,最后i,j会在缺失的数的位置附近
看一下题解:面试题53 - II. 0~n-1 中缺失的数字(二分法,清晰图解)
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论