这是我参加8月更文应战的第15天，活动概略检查：8月更文应战

标题描绘：

268. 丢掉的数字 – 力扣（LeetCode） (leetcode-cn.com)

给定一个包含[0, n]中n个数的数组nums，找出[0, n]这个规划内没有呈现在数组中的那个数。leetcode会员值得买吗

进阶：

  • 你能否数组去重完成线性时间复杂度、仅使用额定常数空间的算法解决此问题?

示例 1：

输入：nums = [3,0,1]
输出：2
阐明：n = 3，由于有 3 个数字异或是什么意思，所以全部的数字都在规划 [0,3] 内。2 是丢掉的数字，由于它没有呈现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2
阐明：n = 2，由于有 2 个数字，所以全部的数字都在规划 [0,2] 内。2 是丢掉的数字，由于它数组排序没有呈现在 nums 中。

示数组和链表的差异例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
阐明：n = 9，由于有 9 个数字，所以全部的数字都在规划 [0,9] 内。算法的有穷性是指8 是丢掉的数字，由于它没有呈现在 nu算法与数据结构ms 中。

示例 4：

输入：nums = [0]
输出：1
阐明：n = 1，由于有 1 个数字，所以全部异或运算的数字都在规划 [0,1] 内。1 是丢掉的数字，由于它没有呈现算法是什么在 nums 中。

提示：

  • n == nums.length
  • $1 <= n <= 10^4$
  • 0 <= nums[i] <= n
  • nums 中的一异或切数字都 绝无仅有

思路剖析

排序

由题意可知，当一个数组是有序的时分，相邻两数一定是相差1的，所以我们将数组排序后很简略就知道缺失的是哪个数字了。

这儿要注意处理鸿异或符号沟状况，缺失的异或同或数字是首位，这个可以放数组和链表的差异在for循环里处理掉，假设丢数组函数的使用办法掉的是末位，则可以在循环外处理，也便是毕竟的兜底回来其实便是for循环傍边没有发生回来。

AC代码

class Solution {
fun missingNum复杂度符号ber(nums: IntArray): Int {
num异或运算法则s.sort()
for ((index, value) in nums数组词.wi复杂度符号thIndex()) {
if (index != value) return ileetcode官网ndex
}
return nums.异或门逻辑表达式size
}
}

数学法

我们可以用 高斯求和公式 求出 [0..n] 的和，减去数组中全部数的和，就得到了缺失的数字。高斯算法与数据结构求和公式即

∑异或门逻辑表达式i=0ni=n(n+1)2sum_{i=0}^{n}i = frac{n(n+1)}{2}

AC代码

class Solution {
fu算法的五个特性n missingNumber(nums: IntArray): Int {
var sum = (1 + nums.size) * nums.size / 2
for(i in数组函数的使用办法 nums){
s数组um -= i
}
return sum
}
}

总结

这题还算简略，但是数学法其实有溢出危险的，或许test case里没有这个状况，所以通过了

其实之前Lee异或门真值表tCode.136 只呈现一次的数字 ()复杂度排序中我们用过异或解题了，这题也可以用这个办法，能防止溢出。

参看

缺失数字 – 丢数组函数的使用办法掉的数字 – 力扣（LeetCode） (leetcode-cn.com)

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。