这是我参加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 只呈现一次的数字 (juejin.cn)复杂度排序中我们用过异或解题了,这题也可以用这个办法,能防止溢出。

参看

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

发表评论

提供最优质的资源集合

立即查看 了解详情