寻找int数组中未出现过的最小正整数
// Copyright 2021 Aesopd Inc.
// License(BSD/GPL/…)
// Author: Aesopd
// This is a problem with 3 vital details of bug, I’ve debugging for 3h just to realize the problem of boundary of traversal.FUCK THAT SHIT DAMN.
Q:
Write a function:
int solution(vector<int> &A);
that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [−1, −3], the function should return 1.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].
采用二分查找法,vector中二分查找法主要难题就是边界值怎么选的问题。
#include<iostream>
#include <algorithm>
using namespace std;
int solution(vector<int> &arr) {
// write your code in C++14 (g++ 6.2.0)
sort(arr.begin(),arr.end());
int left = 0, right = arr.size();//难点1.这里必须是arr.size(),不能是arr.size()-1,最终也不是特别理解,但聚到问题可以在最初边界这里改改试试
bool isfind = true;
int i=1;
while(isfind){
isfind = false;
int l = left,r = right;
while(l < r){
int mid = l + (r - l) / 2;//难点2.这里LeetCode大哥们都这么写,而不是mid = (l + r) / 2;
if(arr[mid] == i){
isfind = true;
break;
}
else if(arr[mid] < i)
l = mid + 1;//难点3.这里缩小查找范围时,l置为mid+1
else // 而要置r的话置为mid就行
r = mid; // 我当时错就错在置l和r都为mid,或者置l=mid+1且r=mid-1,这两种都是错的
}
i++;
}
i--;
return i;
}