2021-04-08

寻找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;
}
上一篇:威尔逊定理--HDU2973


下一篇:第七篇:使用 CUDA 进行计算优化的两种思路