网站在线支付功能,丹阳网站建设方案,购物网站计划书,えっちな秘密基地视频1 题目
给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
2 解法
最笨的方法是从1开始试, 看1在数组里面是否出现过, 2, 3, ....不过时间复杂度是.
2.1 hash
可以考虑…1 题目
给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
2 解法
最笨的方法是从1开始试, 看1在数组里面是否出现过, 2, 3, ....不过时间复杂度是.
2.1 hash
可以考虑用hash, 遍历数组, 把每个元素的值作为key, 遍历完数组之后再从1开始看是否在hash里面. 但是这样做会额外申请一个hash容器, 这样就不是常数级额外空间了, 而是. 于是考虑利用原数组构造所需hash表. 首先要明确一点, 假设数组的元素个数是n, 会有两种情况, 如果数组正好囊括了所有1 ~ n的所有正整数, 那么不存在的最小正整数就是n 1, 但凡有一个元素值不在1 ~ n中, 所求结果就在[1, n]中. 可以考虑遍历数组, 如果元素值value在[1, n]中, 那么就在对应nums[value - 1](n个元素下标从0开始, nums[0]代表第一个元素)标记一下, 证明value是出现过的, 这样最后再遍历nums, 发现第一个没有标记上的元素的索引 1就是所找的最小正整数. 但是怎么标记呢? 比如元素value在[1, n] 中, 那么就要对nums[value - 1]进行标记, 但是还不能丢失该元素的值信息(比如nums[value - 1]也在[1, n]里面, 你改成n 2的话就会丢失原有的信息了), 所以考虑到设置成负值. 这样结尾遍历的时候, 小于零的话证明这个位置被别人标记过, 也就是占位的正整数出现过, 那么大于0的值的下标 1就是第一个结果. 如果遍历到最后还没有返回值, 那么就是n 1, 要这么做的话首先要保证所有元素都为正的, 那么就把非正元素设置为n 1.
代码:
int firstMissingPositive(vectorint nums) {int nums_size nums.size();for (int num: nums) {if (num 0) {num nums_size 1;}}for (int i 0; i nums_size; i ) {if (nums[i] 0) {nums[i] nums_size 1;}}for (int i 0; i nums_size; i ) {int ele_abs abs(nums[i]);if (ele_abs nums_size) {nums[ele_abs - 1] -abs(nums[ele_abs - 1]);}}for (int i 0; i nums_size; i ) {if (nums[i] 0)return i 1;}return nums_size 1;
}
2.2 置换法
