面试题 17.04. 消失的数字
一、题目描述
数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?
二、示例
输入:[3,0,1]
输出:2
输入:[9,6,4,2,3,5,7,0,1]
输出:8
三、实现
方法1 排序后顺序查找
排序,依次查找,如果下一个数不是上一个数加1,则上一个数加1就是消失的数字。
int missingNumber(int* nums, int numsSize) {
// sort
for (int i = numsSize; i > 0; --i) {
int exchange = 0;
for (int j = 1; j < i; ++j) {
if (nums[j - 1] > nums[j]) {
int tmp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = tmp;
exchange = 1;
}
}
if (exchange == 0) {
break;
}
}
// search
for (int i = 0; i < numsSize - 1; ++i) {
if (nums[i] + 1 != nums[i + 1]) {
return nums[i] + 1;
}
}
return -1;
}
这里的排序使用的是简单的冒泡排序时间复杂度O(n2),遍历数组时间复杂度为O(n),总体时间复杂度为O(n2),即便使用更为高效的排序算法,总体时间复杂度不是O(n)。
方法2 利用异或性质
两个相同的数异或为0:x ^ x = 0
并且异或满足交换律:a ^ b ^ c = a ^ c ^ b
让数组的size个数与[0, size-1]共size个数异或,得到的结果再与size异或,最终得到的便是[0, size]中缺的那个整数。文章来源:https://www.toymoban.com/news/detail-417521.html
int missingNumber(int* nums, int numsSize){
int temp = 0;
for(int i = 0; i < numsSize; ++i) {
temp ^= i;
temp ^= nums[i];
}
temp ^= numsSize;
return temp;
}
方法3 利用求和
0-N等差数列公式计算求和结果,然后减数组中的所有元素。文章来源地址https://www.toymoban.com/news/detail-417521.html
int missingNumber(int* nums, int numsSize) {
int sum = (1 + numsSize) * numsSize / 2;
for (int i = 0; i < numsSize; ++i) {
sum -= nums[i];
}
return sum;
}
到了这里,关于【刷题】面试题 17.04. 消失的数字的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!