C语言给定一个未排序的整数数组 nums，找出其中没有出现的最小的正整数。 给出时间复杂度为 O(n) 并且只使用常数级别额外空间的代码

可以使用桶排序的思想，将数组中的数放入对应的桶中，然后遍历桶，找到第一个空桶的下标即为所求。

以下是代码实现：

int firstMissingPositive(int* nums, int numsSize){
    int i;
    for(i = 0; i < numsSize; i++){
        while(nums[i] > 0 && nums[i] <= numsSize && nums[nums[i] - 1] != nums[i]){
            int temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    for(i = 0; i < numsSize; i++){
        if(nums[i] != i + 1){
            return i + 1;
        }
    }
    return numsSize + 1;
}

时间复杂度为 O(n)，空间复杂度为常数级别。

相关问题

用C语言缺失的第一个正数 给定一个未排序的整数数组 nums ，找出其中没有出现过的最小的正整数 要求：时间复杂度为O(n)

可以使用桶排序的思想来解决这个问题，具体步骤如下：

1. 遍历数组，将所有大于等于1且小于等于n的数放入桶中，桶的编号即为数值减1。

2. 再次遍历桶，找到第一个空桶的编号，该编号+1即为所求的最小正整数。

下面是使用C语言实现的代码：

int firstMissingPositive(int* nums, int numsSize){
    for (int i = 0; i < numsSize; i++) {
        // 将所有大于等于1且小于等于n的数放入桶中
        while (nums[i] > 0 && nums[i] <= numsSize && nums[nums[i] - 1] != nums[i]) {
            int temp = nums[i];
            nums[i] = nums[temp - 1];
            nums[temp - 1] = temp;
        }
    }
    // 再次遍历桶，找到第一个空桶的编号，该编号+1即为所求的最小正整数。
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return numsSize + 1;
}

该算法的时间复杂度为O(n)，符合题目要求。

c语言给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

好的，这是一道经典的数组问题。我们可以使用暴力法、哈希表等多种方法来解决。

这里提供一个使用哈希表的解法，时间复杂度为 O(n)：

1. 定义一个哈希表，用于存储数组中每个元素的值和它对应的下标。
2. 遍历数组，对于每个元素 nums[i]，在哈希表中查找是否存在 target - nums[i] 的值。
3. 如果存在，则返回它们的下标；否则将 nums[i] 和 i 存入哈希表中，继续遍历。

代码如下：

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int hash[numsSize]; // 哈希表
    memset(hash, -1, sizeof(hash)); // 初始化为-1
    int* res = (int*)malloc(sizeof(int) * 2); // 存放结果
    *returnSize = 2;
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        if (hash[complement] != -1) { // 找到了
            res[0] = hash[complement];
            res[1] = i;
            return res;
        }
        hash[nums[i]] = i; // 没找到，存入哈希表
    }
    return res;
}