算法题9||查找缺失数字

骑猪看日落 2023-03-01 10:22 18阅读 0赞

## 题目 ##

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzOTIw_size_16_color_FFFFFF_t_70]

## 分析 ##

明显，数组只缺少一个数字，即可利用下标巧妙求解。  
一共进行两次递归：  
1，第一次递归，让数组元素数值与其下标数值（或数组长度）相等；  
2，最大值特殊处理，用变量max标记，若未出现，则直接返回数组长度，否则进行二次递归；  
2，第二次递归，若数组值为最大值，则表示原数组中没有与该下标相等的值，返回对应下标即可。

## 代码 ##

int missingNumber(int* nums, int numsSize){ 
        int i = 0,temp,max = 0;//用max变量标记最大值
        for( ; i < numsSize; i++){ 
            if(nums[i] != i){ //利用下标值，递归让下标值与数组值相等
                if(nums[i] == numsSize){ //若出现最大值，则max=1
                    max = 1;
                    continue;
                }
                //数组值不是最大值（即不会使数组溢出情况下，执行）
                temp = nums[i];
                nums[i--] = nums[temp];
                nums[temp] = temp;
            }
        }
        if(max == 0)    return numsSize;//若最大值没有存在数组中，则返回最大值（即numsSize）
        for(i = 0; i <= numsSize; i++){ //反之，递归判断，若数组值等于最大值，则返回对应下标
            if(nums[i] == numsSize){ 
                return i;
            }
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzOTIw_size_16_color_FFFFFF_t_70 1]

## 其他解法 ##

查看了其他力扣题友的解题方法，发现还可以利用”求和法“求解，提供了新思路，直接将其代码截图贴上来：  
![在这里插入图片描述][20200724090919863.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzOTIw_size_16_color_FFFFFF_t_70]: /images/20230209/4e3d9dec130c453c8a8aec5fc1cfb307.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzOTIw_size_16_color_FFFFFF_t_70 1]: /images/20230209/4c1463ce958143779e509881c879dc0d.png
[20200724090919863.png]: /images/20230209/b171fc3da6614fd5a57a0b23d8e94a65.png