深圳总部企业名单/北京seo优化费用

第一个缺失的正数，给定n个数字，找到第一个缺失的正数，n个数可能包含0 正数 负数。

1 2 3  =》 42 3 5  =》 1-1 2 3 =》1

【思路】

以往的思路，是对应于归位法：即对于一个数num其，所在的位置为【num-1】，若arr[num-1]存在数字，那么继续不断下去，直到出现三种情况：

1. 若当前的数字为0或者负数 那么无法为其寻找位置，跳出循环
2. 若当前的数字大于原先数组长度 那么无法为其寻找位置
3. 若当前的数字num与当前的位置pos 刚好为num=pos+1 即一个环归位完成

整个程序，从i=0 => i=n-1  即搜寻所有位置上的数字不符合的开始进行归位，直到结束

【新思路】

while(arr[i]!=i+1 && arr[i]>0 && arr[i]<n):   //当某个位置的数没有归位正确时，将其归位正确swap(arr[i]，arr[arr[i]-1]);

新思路本质仍然是为数字不断的寻找合适位置，只是采取交换的方式，容易理解

int main()
{int n;cin>>n;vector<int> arr(n);for(int i=0;i<n;i++)cin>>arr[i];for(int i=0;i<n;i++){while(arr[i]!=i+1 && arr[i]>0 && arr[i]<=n)  //i位置的数字没有正确归位swap(arr[i],arr[arr[i]-1]);}bool flag=false;for(int i=0;i<n;i++)if(arr[i]!=i+1)   //没有归位正确{flag=true;cout<<i+1<<endl;break;}if(flag==false)cout<<n+1<<endl;  //若所有数字归位正确 第一个数字就是n+1}