给定一个含n(n>1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组{-5,3,2,3}中未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是。
时间: 2023-05-31 15:19:21 浏览: 181
### 回答1:
题目的意思是给定一个包含n(n>1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组[5,3,2,3]中未出现的最小正整数是1;数组[1,2,3]中未出现的最小正整数是4。
解决这个问题的一个高效算法是将数组中的每个数放在对应的位置上,例如将数字x放在下标为x-1的位置上。然后遍历整个数组,找到第一个不在正确位置上的数字的下标+1,即为结果。如果数组中所有数字都在正确位置上,则答案为n+1。
具体实现时可以使用原地哈希的思想,将数字x交换到下标为x-1的位置上。每次交换后都检查该位置是否已经有了正确的数字,如果是则继续交换直到找到一个正确的位置。如果该位置上已经有了正确的数字,则继续遍历下一个位置。
下面是Python代码实现:
def find_missing_positive(nums):
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
print(find_missing_positive([5,3,2,3])) # 1
print(find_missing_positive([1,2,3])) # 4
### 回答2:
这道题目考查的是算法的实现和优化。我的思路是利用桶排序的思想,把数组中的元素映射到一个桶中,然后从桶的最左边开始往右遍历,找到第一个未出现的正整数。
具体步骤如下:
1. 首先遍历数组,把每个大于0的元素映射到对应的桶中,如果元素小于等于0或者大于n,则不考虑。
2. 从桶的最左边开始往右遍历,找到第一个空桶,其下标加1即为未出现的最小正整数。如果没有找到空桶,则返回n+1。
代码实现如下:
```
int findMinPositive(int* nums, int numsSize){
int* bucket = (int*)calloc(numsSize, sizeof(int)); // 初始化桶为0
for(int i=0; i<numsSize; i++){
if(nums[i]>0 && nums[i]<=numsSize){ // 大于0的元素映射到桶中
bucket[nums[i]-1] = nums[i];
}
}
for(int i=0; i<numsSize; i++){
if(bucket[i]==0){ // 找到第一个空桶
free(bucket);
return i+1;
}
}
free(bucket);
return numsSize+1; // 没有空桶,最小未出现正整数为n+1
}
```
时间复杂度为O(n),空间复杂度为O(n),符合题目要求的时间复杂度尽可能高效。
这个算法的优化点在于空间的优化,即使用一个桶来存储元素的位置信息,而不是使用一个大小为n的哈希表或数组,这样可以降低空间复杂度。
同时,由于桶排序是一种线性时间复杂度的算法,所以时间复杂度也是可以接受的。
### 回答3:
题目要求我们找出未出现的最小正整数,那么我们可以使用桶排序的思想,把这个数组当做一个桶来使用,遍历这个数组,把出现的数字放在对应的桶里面,因为我们只关心未出现的最小正整数,所以我们无需关心这个桶里面存的数字是多少,只需要记录下桶里面存不存在数字就可以了。最后再遍历一遍数组,找到第一个桶里面不存在数字的下标,就是未出现的最小正整数。
具体的实现过程如下:
1.遍历整个数组,将每个出现的数字映射到对应的桶内,找到最大值max。
2.从1开始枚举到max,找到第一个没有出现的数字返回即可。
因为数组的长度为n,遍历一次需要O(n)的时间复杂度,第二次最多枚举到max,所以时间复杂度是O(n+max),其中max可以看成固定值,所以时间复杂度为O(n)。
代码如下:
```python
def find_min_positive(nums):
n = len(nums)
# 把每个数字映射到对应的桶中
bucket = [False] * (n+1)
for num in nums:
if 0 < num <= n:
bucket[num] = True
# 找到第一个没有出现的数字
for i in range(1, n+1):
if not bucket[i]:
return i
# 如果都出现了,返回n+1
return n+1
```
综上所述,我们可以通过桶排序的思想来解决这个问题,时间复杂度为O(n),是一种高效的算法。
阅读全文