原创

268. 缺失数字

链接

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]
输出: 2

示例2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:

你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

func missingNumber(nums []int) int {
    	// 因为没有跳过的数,所以求出长度的和,然后减去每一项的值
	max := len(nums) * (len(nums) + 1) / 2

	for _, j := range nums {
		max -= j
	}
	return max
}

解法2

解法2

func missingNumber(nums []int) int {
	xor := 0

	for i, n := range nums {
		xor ^= i ^ n
	}

	// 所有的 i 再加上 len(nums),就相当于 0,1,...,n。
	// 利用 相同的数异或为0,及其交换律
	// xor 最后的值,就是那个缺失的数

	return xor ^ len(nums)
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 268. 缺失数字

    给定一个包含 0, 1, 2, …, n 中 n 个数的序列,找出 0 … n 中没有出现在序列中的那个数。

    Michael阿明
  • ​LeetCode刷题实战268:丢失的数字

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • LeetCode268. 缺失数字

    mathor
  • Swift 缺失数字 - LeetCode

    给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

    韦弦zhy
  • 【leetcode刷题】T194-缺失数字

    https://leetcode-cn.com/problems/missing-number

    木又AI帮
  • DFS、异或-LeetCode 257、258、268、283

    使用dfs算法获得每条路径,注意在生成字符串时可以使用string类型,可以直接使用加法操作对字符串进行拼接得到最终结果!

    算法工程师之路
  • 打卡群刷题总结0605——缺失数字

    链接:https://leetcode-cn.com/problems/missing-number

    木又AI帮
  • LeetCode 1228. 等差数列中缺失的数字

    我们会从该数组中删除一个 既不是第一个 也 不是最后一个的值,得到一个新的数组 arr。

    Michael阿明
  • 在裸机与虚拟机上运行容器:性能和优点

    根据最近的研究,Docker正在像野火一样蔓延,特别是在企业中,它的采用率从2015年的13%上升到了27%以上;另有35%的公司计划使用Docker。根据这些...

    首席架构师智库

扫码关注云+社区

领取腾讯云代金券