这是我参加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)