【刷题】面试题 17.04. 消失的数字

这篇具有很好参考价值的文章主要介绍了【刷题】面试题 17.04. 消失的数字。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


面试题 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]中缺的那个整数。

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2.数据结构面试题--消失的数字

    数组nums包含从0到n的所有整数,但是其中缺了一个,请编写代码找出那个缺失的整数,你有办法O(N)时间内完成吗? 如果下一个数不是上一个数+1,那么上一个数字+1就是消失的数字 冒泡排序的话时间复杂度是O(n^2) qsort排序的话是O(N logN) 需要用一个循环来判断如果下一个数不是上一个

    2024年02月16日
    浏览(32)
  • LeetCode:面试题:消失的数字——时间复杂度

    题目:数组nums中包含0~n的所有整数,但其中缺失了一个数,请写代码找出那个缺失的整数,要求在时间复杂度为O(N)的时间内完成 思路1:冒泡排序+遍历(下一个数不等于上一个数+1,这个下一个数就是消失的数) 世间复杂度O(logN*N) 代码: 运行结果: 思路2:0+N利用等

    2024年02月16日
    浏览(37)
  • 17:00面试,17:04就出来了 ,问的实在是太...

    从外包出来,没想到算法死在另一家厂子 自从加入这家公司,每天都在加班,钱倒是给的不少,所以也就忍了。没想到8月一纸通知,所有人不许加班,薪资直降30%,顿时有吃不起饭的赶脚。 好在有个兄弟内推我去了一家互联网公司,兴冲冲见面试官,没想到一道题把我给问

    2023年04月20日
    浏览(45)
  • C语言--消失的数字

    时间复杂度:O(N) 空间复杂度:O(N) 时间复杂度:O(N) 时间复杂度:O(N) 时间复杂度:O((N+1)*logN)

    2024年02月11日
    浏览(30)
  • 【leetcode】消失的数字

    大家好,我是苏貝,本篇博客带大家刷题,如果你觉得我写的还不错的话,可以给我一个赞👍吗,感谢❤️ 点击查看题目 通过2个for循环,遍历查找0-n中缺少的数字,比较简单,不写,时间复杂度为O(N^2) 点击去了解异或,位置在④.3 异或:两个整数的相同位置:相同为0,不

    2024年01月22日
    浏览(41)
  • leetcode消失的数字

    数组 nums 包含从 0 到 n 的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在 O ( n ) O(n) O ( n ) 时间内完成吗? 示例 1: 输入:[3,0,1] 输出:2 leetcode链接:消失的数字 ⭕️ 思路1: 第一种思路时间复杂度 O ( N ) O(N) O ( N ) ,空间复杂度 O ( N ) O(N) O ( N ) 。

    2024年02月11日
    浏览(33)
  • 每日一题——找到消失的数字

    题目链接 一个长度为 n 的数组中所有数据的范围在 [1,n] 内,题目要求我们找出在 [1,n] 范围内,但数组中没有出现的数字 如果可以使用额外空间,那这题就好办了。我们直接创建一个相同大小的数组,数组的每个位置代表 [1,n] 的每个元素,然后遍历数组计数就行。 我们这里

    2024年02月15日
    浏览(36)
  • 消失的数字(c语言多种解法)

    该题目取自力扣(LeetCode)面试题 17.04. 消失的数字 该题目主要考察时间复杂度的把握,题目如下: 数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗? 示例 1: 输入:[3,0,1] 输出:2 示例 2: 输入:[9,6,4,2,3,5,7,

    2024年02月21日
    浏览(34)
  • Leetcode448. 找到所有数组中消失的数字

    题目来源:448. 找到所有数组中消失的数字 set 是一个集合类型的容器,里面的元素具有唯一性,并且所有元素都会根据元素的键值自动被排序,以红黑树为底层数据结构。 我们使用集合set记录nums数组的元素,再遍历set找出找到所有的数组nums中消失的数字。 代码: 结果:

    2024年02月03日
    浏览(42)
  • 【快乐手撕LeetCode题解系列】——消失的数字

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2024年02月01日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包