西安网站seo推广,wordpress联系方式代码,jsp网站开发 心得,wordpress字体路径设置目录
暴力排序
桶排序
桶排序Set
桶排序分治思想
官方题解
桶排序数组内标记
桶排序额外数组标记#xff08;更好理解#xff09; 给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额…目录
暴力排序
桶排序
桶排序Set
桶排序分治思想
官方题解
桶排序数组内标记
桶排序额外数组标记更好理解 给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1 输入nums [1,2,0]
输出3示例 2 输入nums [3,4,-1,1]
输出2示例 3 输入nums [7,8,9,11,12]
输出1提示 1 nums.length 5 * 10^5-2^31 nums[i] 2^31 - 1 暴力排序
先不考虑题目要求的时间、空间复杂度先简单暴力的做出来结果给自己一点信心有时候想要按照题目要求直接做出最终结果太难先有一个能用的方案也有助于打开后续的思路。
先来暴力排序法
对输入数据过滤后排序遍历一遍排序后的数组就可以找到最小的正整数
// 给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。
class Solution {func firstMissingPositive(_ nums: [Int]) - Int {// 先把不合规的 负数和0 去除let nums nums.filter { value inreturn value 0}// 排序后的都是正整数数组let sortNum nums.sorted()var findSuccess falsevar result 0// 查找最小的正整数for (i,num) in sortNum.enumerated() {// 第一个数据与1比较,// 为1 就继续向后查找// 非1 就找到了最小正整数,if i 0 {if num 1 {continue} else {result 1findSuccess truebreak}} else {// 当前数与前一个对比, 可以相等(有这样的测试case[0,1,1,2,2]), 可以差为1,// 如果差大于1,那说明找到了最小的正整数let preNum sortNum[i-1]if num - preNum 1 {result preNum 1findSuccess truebreak}}}// 如果没有在前面和中间找到最小的正整数, 那就是在最后了, 比如[1,2,3]这样的数组// 有可能全是负数过滤完之后sortNum数组为空那1就是最小的整数if findSuccess false {result (sortNum.last ?? 0) 1}return result}
} 暴力法用到了排序时间复杂度为O(N*logN)空间复杂度为O(1) 桶排序
在排序算法中还有一种特殊的排序算法 桶排序。使用桶排序的的时间复杂度为O(N)可以尝试使用桶排序的变种来做。
先不考虑空间假设桶的空间无限
准备一个2^31大的数组作为桶bucket[]遍历输入数据出现数字k就bucket[k]1标志这个数字出现从1开始向上找bucket中第一个出现0的数这个数就是最小的正整数
桶排序Set
元素的大小范围太大2^31 - 1但是数量有限 5*10^5可以用一个set来存所有出现的数字然后从1开始向上枚举所有正整数找出不在set中的数据。 // 给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。
class Solution {func firstMissingPositive(_ nums: [Int]) - Int {// 元素的大小范围太大,但是数量有限以数组的count作为集合的大小var set SetInt.init(minimumCapacity: nums.count)nums.forEach { value inif value 0 {set.insert(value)}}var result 1while true {if set.contains(result) {result 1} else {break}}return result}
} 这个满足时间复杂度为O(N)但是需要的空间复杂度也为O(N)同时set中的hash计算也比较费时实际执行时间变化不大。
桶排序分治思想
基于桶排序还有一种思路桶排序的问题就在这个桶不能无限大那就限定桶的大小为10000一次分治10000条数据针对这10000条数据在尝试用桶排序来处理
填充桶内数据在遍历的输入数据的时候把1-9999之间的数字k放入桶中标记bucket[k] 1 超过1000010000的数据不考虑。检查桶内数据从1开始遍历桶中的数据 如果在桶中找到一个值bucket[k] 为0 那就是找到了最终结果如果在这个桶内找不到为0的值把原数据中的所有值都 - 9999在重新加入桶中重复第二步。
如果桶的范围限定为1相当于每次查找数组的最小值然后每次减1退化成了选择排序法。
class Solution {static let ArrayCount 10000var bucket Array(repeating: 0, count: Solution.ArrayCount)func firstMissingPositive(_ nums: [Int]) - Int {// 建一个10000个数组的桶,遍历往里面放值// 遍历这个桶,找到有空值就输出// 找不到,把输入数组每个值减9999,在重新放到桶中,// 遍历这个桶,找到有空值就输出找不到就重复减9999重新加桶var result 0var count 0var nums numswhile true {self.fillBucket(nums)let (isSuccess, tempResult) self.checkBucket()if isSuccess {result tempResultbreak} else {nums self.updateNumber(nums)self.cleabBucket()count 1if nums.count 0 {result 1break}}}result count * (Solution.ArrayCount-1) resultreturn result}// 拿数据填充桶func fillBucket(_ nums: [Int]) {for num in nums {if num 0 num Solution.ArrayCount {self.bucket[num] 1}}}// 检查桶内有没有空值func checkBucket() - (Bool, Int) {var isSuccess falsevar result 0for (i,value) in bucket.enumerated() {if (i 0) {continue}if (value 0) {isSuccess trueresult ibreak}}return (isSuccess, result)}// 清空桶内的上一轮数据的标志位func cleabBucket() {bucket bucket.map { _ inreturn 0}}// 原数组的数据更新func updateNumber(_ nums: [Int]) - [Int] {var newArray [Int]()for num in nums {if (num Solution.ArrayCount) {// 负数, 已经往数组里放过的数,不在追加到新数组中} else {let newNum num - Solution.ArrayCount 1newArray.append(newNum)}}return newArray}
} 虽然使用了桶排序的思想时间复杂度为O(N*logN)空间复杂度使用了固定长度的数组为O(1) 官方题解
最后看了官方题解基于桶排序使用额外set的思路但是使用数组内的数据替换set的使用。做到了空间复杂度为O(1)。
桶排序数组内标记
官方题解里面提到了1个重要的结论对于一个长度为 N 的数组其中没有出现的最小正整数只能在 [1,N1] 中。
这是因为如果 [1,N]都出现了那么答案是 N1比如[1,2,3]这样的数组如果出现任何一个不在[1,N]的数都将挤占原有的一个位置那最小正整数必定是在[1,N]中。 比如[1,5,2] [1,2,-1]
这样一来我们将所有在 [1,N]范围内的数放入哈希表也可以得到最终的答案。而给定的数组恰好长度为 N这让我们有了一种将数组设计成哈希表的思路
我们对数组进行遍历对于遍历到的数 x如果它在 [1,N]的范围内那么就将数组中的第 x−1个位置注意数组下标从 0 开始打上「标记」标记x出现过。在遍历结束之后如果所有的位置都被打上了标记那么答案是 N1否则答案是最小的没有打上标记的位置加 1。
那么如何设计这个「标记」呢由于数组中的数没有任何限制因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质由于我们只在意 [1,N]中的数因此我们可以先对数组进行遍历把不在 [1,N]范围内的数修改成任意一个大于 N 的数例如 N1。这样一来数组中的所有数就都是正数了因此我们就可以将「标记」表示为「负号」。算法的流程如下
我们将数组中所有小于等于 0 的数修改为 N1我们遍历数组中的每一个数 x它可能已经被打了标记因此原本对应的数为 ∣x∣其中 ∣∣ 为绝对值符号。如果 ∣x∣∈[1,N]那么我们给数组中的第 ∣x∣−1个位置的数添加一个负号这个负号就是标记标记|x| 出现过。注意如果它已经有负号不需要重复添加在遍历完成之后 如果数组中的每一个数都是负数那么答案是 N1否则答案是第一个正数的位置加 1。 class Solution {func firstMissingPositive(_ nums: [Int]) - Int {// 第一个遍历, 把所有的负数和0标记改为 arrayCount1let arrayCount nums.countvar newArray: [Int] nums.map { num invar result numif result 0 {result arrayCount 1}return result}// 第二个遍历, 把在[1,arrayCount]之间的数打上负数标记, 下表1即为原始值for value in newArray {let originValye abs(value)if originValye arrayCount {newArray[originValye-1] -abs(newArray[originValye-1])}}var findSuccess falsevar result 0// 第三个遍历, 找出结果for (i,num) in newArray.enumerated() {if num 0 {// 说明 i1 对应的值存在} else {// 说明找到了findSuccess trueresult i 1break}}if findSuccess false {result arrayCount 1}return result}
}
使用官方的题解确实快了不少只需3次遍历即可完成。时间复杂度为O(N)空间复杂度为O(1)。 桶排序额外数组标记更好理解
如果上面的思路没有理解到也没关系现在的计算机内存大小一般不是瓶颈使用额外大小的数组来做标记更好理解。
生成一个大小为N的桶初始化内部元素为0遍历输入数据在[1,N]之间的数字加入桶中标记为1遍历桶中数据 出现第一个标记为0的元素下标1即为结果。没有出现为0的元素N1即为结果。
class Solution {func firstMissingPositive(_ nums: [Int]) - Int {// 第一个遍历, 把[1,N]之间的数字放入桶中, 并做好标记let arrayCount nums.countvar bucket ArrayInt.init(repeating: 0, count: arrayCount)nums.forEach { num invar result numif num 1 num arrayCount {bucket[num-1] 1}}var findSuccess falsevar result 0// 第二个遍历, 找出结果for (i,num) in bucket.enumerated() {if num 0 {// 说明 这个数字不在桶中, 找到了findSuccess trueresult i 1break}}if findSuccess false {result arrayCount 1}return result}
} 这个满足时间复杂度为O(N)但是需要的空间复杂度也为O(N)相当于对set方案的一次深度优化
优化点1使用数组的偏移替换复杂的hash计算。
优化点2充分利用下面结论减少了不必要的数据处理。
对于一个长度为 N 的数组其中没有出现的最小正整数只能在 [1,N1] 中。
