给你一个未排序的整数数组nums,请你找出其中没有出现的最小整数
时间: 2023-05-28 10:01:23 浏览: 61
可以利用桶排序的思想来解决这个问题。具体步骤如下:
1. 初始化一个大小为n+1的桶,桶的下标从1到n+1。
2. 遍历数组,如果nums[i]大于0且小于等于n,就将桶的对应位置标记为1。
3. 再次遍历桶,找到第一个未被标记的下标,即为没有出现的最小整数。
4. 如果遍历完桶都没有找到未被标记的下标,说明所有的整数都出现了,没有缺失的整数,返回n+1。
代码如下:
```python
def findMissingNum(nums):
n = len(nums)
bucket = [0] * (n+1) # 初始化桶
for i in range(n):
if nums[i] > 0 and nums[i] <= n:
bucket[nums[i]] = 1 # 标记桶
for i in range(1, n+1):
if bucket[i] == 0:
return i # 找到第一个未标记的下标
return n+1 # 所有的整数都出现了,返回n+1
```
测试:
```python
>>> nums = [3, 4, -1, 1]
>>> findMissingNum(nums)
2
>>> nums = [1, 2, 0]
>>> findMissingNum(nums)
3
>>> nums = [7, 8, 9, 11, 12]
>>> findMissingNum(nums)
1
```
相关问题
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
题目描述:
给定一个未排序的整数数组,找出其中没有出现的最小的正整数。
解题思路:
我们可以使用桶排序的思想,将每个数放到它应该在的位置上,然后再遍历一遍数组,找到第一个不在它应该在的位置上的数,这个数就是没有出现的最小正整数。
具体实现:
1. 遍历数组,将每个数放到它应该在的位置上,例如,数 5 应该放在数组下标为 4 的位置上。
2. 再遍历一遍数组,找到第一个不在它应该在的位置上的数,这个数就是没有出现的最小正整数。
3. 如果数组中所有的数都在它应该在的位置上,那么最小正整数就是数组长度加 1。
代码实现:
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = ; i < n; i++) {
while (nums[i] > && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[i], nums[nums[i] - 1]);
}
}
for (int i = ; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
};
给你一个未排序的整数数组nums,请你找出其中没有出现的最小整数,用java
解答:
可以使用桶排序的思想,将数组中所有正数按照其值放到对应的下标位置上。然后遍历数组,寻找第一个不满足nums[i] = i + 1的位置i,那么i+1就是没有出现过的最小整数。
代码如下:
```java
public int findMissingNumber(int[] nums) {
int n = nums.length;
// 将所有正数放到对应的下标位置上
for (int i = 0; i < n; i++) {
// while循环保证交换来的数一定放到了它应该放的位置上
while (nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i]) {
swap(nums, i, nums[i]-1);
}
}
// 查找第一个不满足nums[i] = i+1的位置
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// 都满足,说明前n个正数都出现了,返回n+1
return n + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
```
时间复杂度:O(n)。
空间复杂度:O(1)。