leetcode数组常见面试算法题

发表于 更新于 分类于 Changyan：
数组常见面试算法题
1
https://github.com/labuladong/fucking-algorithm

什么叫ARTS？

每周完成一个ARTS：

  1. Algorithm：每周至少做一个 leetcode 的算法题
  2. Review：阅读并点评至少一篇英文技术文章
  3. Tip：学习至少一个技术技巧
  4. Share：分享一篇有观点和思考的技术文章

作者：陈皓
链接：https://www.zhihu.com/question/301150832/answer/529809529
来源：知乎

Reverse String

翻转字符串char[]，O(1)空间复杂度。

1
2
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
方法一
  1. 从数组的头尾同时遍历，交换方法为a=a^b;b=a^b;a=a^b;
  2. 如果中间还剩一个，就不处理。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void reverseString(vector<char>& s) {
        if(s.size()<=1)
            return;
        for(int i=0,j=s.size()-1;i<j;i++,j--) {
            s[i]=s[i]^s[j];
            s[j]=s[i]^s[j];
            s[i]=s[i]^s[j];
        }
    }
};
方法二
  1. 直接调用算法
1
2
3
4
5
6
class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(), s.end());
    }
};

Reverse Integer

32位有符号整形，将数字部分颠倒，如果颠倒后异常，需要处理为0。

1
2
Input: -123
Output: -321
方法一
  1. 需要依次取出各位至数组中。
  2. 然后采用算法颠倒。
  3. 再依次打包成整数，如果溢出，再进行处理。如果a*b>max，则有a>max/b。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool isOverFlow(int a, int b) {
        if(a>0 && b>0) 
            return (INT_MAX-a)/10<b;
        else if(a<0 && b<0)
            return (INT_MIN-a)/10>b;
        else 
            return false;
    }
    
    int reverse(int x) {
        vector<int> temp;
        int y=0;
        while(x/10) {
            temp.push_back(x%10);
            x/=10;
        }
        temp.push_back(x%10);
        for(int i=0;i<temp.size();i++) {
            if(isOverFlow(temp[i], y))
                return 0;
            y=y*10+temp[i];
        }
        return y;
    }
};
方法二
  1. 依次取个位的数，同时将这个数放在最高位组合出倒数，一次循环完成。
  2. 在循环的过程中，不断检测是否会溢出，如果即将溢出，则直接返回0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isOverflow(int a, int b) {
        if(a>0 && b>0) {
            return a>(INT_MAX-b)/10;
        } else if(a<0 && b<0) {
            return a<(INT_MIN-b)/10;
        } else {
            return false;
        }
    }
    
    int reverse(int x) {
        int res=0;
        while(x) {
            int tmp=x%10;
            if(isOverflow(res, tmp))
                return 0;
            res=res*10+tmp;
            x/=10;
        }
        return res;
    }
};

First Unique Character in a String

给一个字符串，找到第一个不是重复的字母，给出地址，在字符串只考虑小写字母的前提下。

1
2
3
4
5
s = "leetcode"
return 0.

s = "loveleetcode",
return 2.
方法一
  1. 从前往后依次将字母存入int数组[26]，index为字母，value为个数，由于个数可能有很多，得用int数组才行。
  2. 将字符串套入数组检查，找到只出现一次的第一个字母，即value==1，此时的i为地址。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int firstUniqChar(string s) {
        array<int, 26> freq;
        freq.fill(0);
        for(int i=0;i<s.length();i++) {
            freq[s[i]-'a']++;
        }
        for(int i=0;i<s.length();i++) {
            if(freq[s[i]-'a']==1) // freq用来做参考的
                return i;
        }
        return -1;
    }
};
方法二
  1. 从前往后依次存入unordered_map，key为字母，value为个数。
  2. 将字符串套入map中检查，找到只出现一次的第一个字母，map的value==1，此时的i为地址。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> freq;
        for(int i=0;i<s.length();i++) {
            freq[s[i]]++;
        }
        for(int i=0;i<s.length();i++) {
            if(freq[s[i]]==1)
                return i;
        }
        return -1;
    }
};
方法三

优化点思考，第二轮查找第一个单数的时候不需要重新遍历字符串了，直接遍历更新的字典找到第一个单数。

  1. 遍历字符串，更新字典，包括是哪个字符、字符的位置、字符出现的次数。需要用到pair<int, int>
  2. 遍历字典，找到字符出现次数等于1且字符的位置最小的那个位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char,pair<int,int>> dic;
        int index=s.length();
        for(int i=0;i<s.length();i++) {
            dic[s[i]].first=i;
            dic[s[i]].second++;
        }
        for(auto& x: dic) {
            if(x.second.second==1)
                index=index<x.second.first?index:x.second.first; // 要找出最小值
        }
        if(index==s.length())
            return -1;
        return index;
    }
};

Valid Anagram

判断s是否为t的同字母异序词

1
2
Input: s = "anagram", t = "nagaram"
Output: true
方法一
  1. 依次遍历字符串s，建立int[26]数组，存入的是该遍历到的字符个数。
  2. 再依次遍历字符串t，检索之前建立的数组，判断遍历到的该字符是否个数为0，否则不是同字母异序词，如果大于0，直接做减减处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length()!=t.length())
            return false;
        array<int, 26> freq;
        freq.fill(0);
        for(int i=0;i<s.length();i++) {
            freq[s[i]-'a']++;
        }
        for(int j=0;j<t.length();j++) { // freq里面大于0的值用来证明为同字母
            if(freq[t[j]-'a'])
                freq[t[j]-'a']--;
            else
                return false;
        }
        return true;
    }
};
方法二
  1. 依次遍历字符串s，建立字典，存入的是该遍历到的字符个数。
  2. 再依次遍历字符串t，检索之前建立的字典，判断遍历到的该字符是否个数为0，否则不是同字母异序词，如果大于0，直接做减减处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length()!=t.length())
            return false;
        unordered_map<int,int> freq; // 直接用hash
        for(int i=0;i<s.length();i++) {
            freq[s[i]]++;
        }
        for(int j=0;j<t.length();j++) {
            if(freq[t[j]])
                freq[t[j]]--;
            else
                return false;
        }
        return true;
    }
};

Valid Palindrome

判断字符串是否为回文，假设字符串仅考虑由字母数字组成，忽略大小写，假设空字符为回文。

1
2
Input: "A man, a plan, a canal: Panama"
Output: true
方法一
  1. 双指针方案，从头和从尾依次遍历并对比，出现不同则退出。
  2. 怎么去掉空格，判断大小写，去掉其他符号，注意全都是其他字符串的情况或直接用isalnum函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    char getValue(char& c) {
        if(c>=48 && c<=57)
            return c;
        else if(c>=65 && c<=90) {
            return c;
        } else if(c>=97 && c<=122) {
            return c-32;
        } else 
            return 0;
    }
    
    bool isPalindrome(string s) {
        int len=s.length();
        if(len==0)
            return true;
        for(int i=0,j=len-1;i<j;i++,j--) {
            char a=getValue(s[i]);
            while(a==0&&i<j) { // 去掉其它符号
                a=getValue(s[++i]);
            }
            char b=getValue(s[j]);
            while(b==0&&i<j) {
                b=getValue(s[--j]);
            }
            if(a!=b) {
                return false;
            }
        }
        return true;
    }
};
方法二
  1. 同样是双指针方法，只是写法不同，先找到alnum字符，采用while if结构，如果不是alnum字符，则进入循环，再查找，只有同时满足时，才进行对比。
  2. 进行对比，不同则退出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isPalindrome(string s) {
        int len=s.length();
        if(len==0)
            return true;
        int i=0, j=len-1;
        while(i<j) {
            if(!isalnum(s[i])) {
                i++;
            } else if(!isalnum(s[j])) {
                j--;
            } else {
                if(tolower(s[i])!=tolower(s[j]))
                    return false;
                i++;
                j--;
            }
        }
        return true;
    }
};

String to Integer (atoi)

将字符串转换为数字，如果首部有空格则忽略，其他非数字字符，则返回0，末尾含有字母则忽略，需要考虑负数，数字范围为[−231, 231 − 1]。

1
2
3
4
5
6
7
8
9
10
11
12
Input: "   -42"
Output: -42
  
Input: "4193 with words"
Output: 4193
  
Input: "words and 987"
Output: 0
  
Input: "-91283472332"
Output: -2147483648

方法一
  1. 从头遍历字符串，如果发现有空格则跳过，如果发现是正负符号，则赋给符号变量。
  2. 再接着遍历，只对数字进行处理，同时计算数值大小（提前计算是否溢出，如果溢出了，边界值应该怎么给），如果发现有非数字字符，则退出遍历，返回计算结果。
  3. 难点：判断是非溢出，及其处理措施？如果a>=0,b>=0，则a*10+b>INT_MAX转化为a>(INT_MAX-b)/10；如果a<0,b<=0(一定要包括0)，则a*10+b<INT_MIN转化为a<(INT_MAIN-b)/10；对于没有溢出的情况计算结果为a=a*10+b.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    bool overFlowValue(int& a, int b) {
        if(a>=0 && b>=0 && a>(INT_MAX-b)/10) {
            a = INT_MAX;
            return true;
        } else if(a<0 && b<=0 && a<(INT_MIN-b)/10) {
            a = INT_MIN;
            return true;
        } else {
            a = a*10+b;
            return false;
        }
    }
    
    int myAtoi(string str) {
        int flag=1, value=0, got=0;
        for(int i=0;i<str.length();i++) {
            if(got && (str[i]==43 || str[i]==45 || str[i]==32)) // + - (space)
                break;
            if(!got && str[i]==32) // space
                continue;
            if(!got && str[i]==43) { // +
                got=1;
                continue;
            } else if(!got && str[i]==45) { // -
                got=1;
                flag=-1;
                continue;
            }
            if(flag==-1 && value>0)
                value*=-1;
            if(str[i]>=48 && str[i]<=57) { // 0-9
                got=1;
                if(overFlowValue(value, (str[i]-48)*flag)) {
                    break;
                }
            } else {
                break;
            }
        }
        return value;
    }
};

方法二
  1. 对前缀进行完善，空格分while循环进行判断，正负号只判断一次，最后再进行数字判断。
  2. 对溢出部分进行完善，如何判断a*10+b>INT_MAX？
  3. a*10>INT_MAX
  4. a*10==INT_MAX && b>INT_MAX%10
  5. 针对以上两种情况，如果符号位为正，则返回INT_MAX，如果符号位为负，则返回INT_MIN。比如[-10,9]，当取直为10时，10>9，如果是负数，返回-10，如果是正数，返回9.
  6. 其他情况，返回a*10+b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int myAtoi(string str) {
        int flag=1, value=0;
        int i=0;
        while(str[i]==' ') i++; // 去掉空格
        if(str[i]=='-') {
            flag=-1;
            i++;
        } else if(str[i]=='+') {
            i++;
        }
        for(;i<str.length();i++) {
            if(str[i]>='0' && str[i]<='9') {
                if(value>INT_MAX/10 ||(value==INT_MAX/10 && str[i]-'0'>(INT_MAX%10))) { // 最后一位要考虑
                    if(flag==1)
                        return INT_MAX;
                    else
                        return INT_MIN;
                }
                value=value*10+(str[i]-'0');
            } else {
                break;
            }
        }
        return value*flag;
    }
};

Implement strStr()

找到当前字符串在另外一个字符串中出现的位置，空字符串按照0处理，找不到返回-1。

1
2
3
4
5
6
Input: haystack = "hello", needle = "ll"
Output: 2
  
Input: haystack = "aaaaa", needle = "bba"
Output: -1

方法一
  1. 两个字符串都从0开始遍历，同时进行比较，如果比较有相同字符，则needle指针加加，如果没有相同字符，则needle置0，haystack指针回退到刚开始对比的下一个位置（重要）。
  2. 如果任意一个遍历完，则退出，如果是needle遍历完，还要返回haystack的指针位置-needle长度的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.length()==0)
            return 0;
        for(int i=0,j=0;i<haystack.length();) {
            if(haystack[i]==needle[j]) {
                j++;
                i++;
                if(j==needle.length())
                    return i-j;
            } else {
                i=i-j+1;
                j=0;
            }
        }
        return -1;
    }
};

方法二
  1. 使用两个while循环结构，这样就不需要特意进行回退了，但是时间复杂度变大了。
  2. 两个字符串都从0开始遍历，均在内循环进行，同时进行比较，如果有相同的字符，则内循环加加，否则退出内循环。
  3. 如果外循环遍历完，则退出，如果内循环遍历完，则当前的外循环位置即为需要的地址。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.length()==0)
            return 0;
        for(int i=0;i<haystack.length();i++) {
            for(int j=0;j<needle.length();j++) {
                if(haystack[i+j]!=needle[j])
                    break;
                if(j==needle.length()-1)
                    return i;
            }
        }
        return -1;
    }
};

Count and Say

count-and-say序列是整数序列，前五个术语如下：

1
2
3
4
5
1.     1
2.     11
3.     21
4.     1211
5.     111221

第二个数：一个1，第三个数，两个1，第四个数，一个2，一个1，第五个数，一个1，一个2，两个1.

给出5，要求返回111221.

方法一
  1. 从原始字符串前面开始遍历，个数++，遇到不同的数或者原始字符串末尾，则将上一个字符出现的次数以及是哪个字符添加的新字符串末尾。
    1. 如果只是不同的数，清空个数。
    2. 如果遇到末尾，则将新字符串赋值给原字符串，并清空新字符串／个数，最后退出遍历。
  2. 依次递归到第n个，返回此时的字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string countAndSay(int n) {
        string oldRes="1";
        string newRes="";
        if(n==1)
            return oldRes;
        int num=0;
        for(int x=1;x<n;x++) {
            for(int i=0;i<oldRes.length();i++) {
                num++;
                if(i<oldRes.length()-1 && oldRes[i]!=oldRes[i+1]) { // 有多少个这样的数
                    newRes.append(to_string(num));
                    newRes.push_back(oldRes[i]);
                    num=0;
                    continue;
                }
                if(i==oldRes.length()-1) {
                    newRes.append(to_string(num));
                    newRes.push_back(oldRes[i]);
                    num=0;
                    oldRes=newRes;
                    newRes.clear();
                    break;
                }
            }
        }
        return oldRes;
    }
};
方法二
  1. 优化点：for循环可以转化为while循环
  2. 将赋值的部分提取出来，关键在于怎么找到变化的临界点或者字符串的末尾，只要任意一个不满足就表明是边界了，故用&&语句比较合适。
  3. 使用+语句，减少语句。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string countAndSay(int n) {
        if(n==0)
            return "";
        if(n==1)
            return "1";
        string oldStr="1";
        string newStr;
        while(--n) {
            newStr="";
            for(int i=0,num;i<oldStr.length();i++) {
                num=1;
                while(i<oldStr.length()-1 && oldStr[i]==oldStr[i+1]) {
                    i++;
                    num++;
                }
                newStr+=to_string(num)+oldStr[i];
            }
            oldStr=newStr;
        }
        return oldStr;
    }
};

Longest Common Prefix

找出字符串数组的共有前缀：

1
2
3
Input: ["flower","flow","flight"]
Output: "fl"

方法一
  1. 设置公共前缀str为第一个字符串。
  2. 再str与下一个进行对比，更新公共str。
  3. 直到对比完所有字符串。
  4. 如果发现str为空，直接退出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0)
            return "";
        string str=strs[0];
        for(int i=1;i<strs.size();i++) {
            int j=0;
            while(j<str.length() && str[j]==strs[i][j]) {
                j++;
            }
            str=str.substr(0, j);
        }
        return str;
    }
};

方法二
  1. 先对数组进行长度的排序。
  2. 只对第一个和最后一个进行对比，找出公共部分即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0)
            return "";
        sort(strs.begin(), strs.end());
        int i=0;
        while(i<strs[0].length() && strs[0][i]==strs[strs.size()-1][i]) {
            i++;
        }
        return strs[0].substr(0,i);
    }
};

寻找中心索引

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

先求出数组总和sun，
要使得下标i左右元素和相等，sum - nums[i] 等于 左侧元素和的2倍；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int pivotIndex(vector<int>& nums) {
    int sum = 0;
    int left = 0;
    for(int num : nums) {
        sum += num;
    }
    for(int i = 0; i < nums.size(); i++) {
        if (sum - nums[i] == 2*left) {
            return i;
        }
        left += nums[i];
    }
    return -1;
}

旋转矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

这里的方法不需要记录已经走过的路径，所以执行用时和内存消耗都相对较小

  1. 首先设定上下左右边界
  2. 其次向右移动到最右，此时第一行因为已经使用过了，可以将其从图中删去，体现在代码中就是重新定义上边界
  3. 判断若重新定义后，上下边界交错，表明螺旋矩阵遍历结束，跳出循环，返回答案
  4. 若上下边界不交错，则遍历还未结束，接着向下向左向上移动，操作过程与第一，二步同理
  5. 不断循环以上步骤，直到某两条边界交错，跳出循环，返回答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector <int> ans;
    if(matrix.empty()) return ans; //若数组为空，直接返回答案
    int up = 0; //赋值上下左右边界
    int down = matrix.size() - 1;
    int left = 0;
    int right = matrix[0].size() - 1;
    while(true)
    {
        for(int i = left; i <= right; ++i) ans.push_back(matrix[up][i]); //向右移动直到最右
        if(++ up > down) break; //重新设定上边界，若上边界大于下边界，则遍历遍历完成，下同
        for(int i = up; i <= down; ++i) ans.push_back(matrix[i][right]); //向下
        if(-- right < left) break; //重新设定有边界
        for(int i = right; i >= left; --i) ans.push_back(matrix[down][i]); //向左
        if(-- down < up) break; //重新设定下边界
        for(int i = down; i >= up; --i) ans.push_back(matrix[i][left]); //向上
        if(++ left > right) break; //重新设定左边界
    }
    return ans;
}

最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

对于 nums 中的任意两个值 a 和 b，我们无法直接从常规角度上确定其大小/先后关系。

但我们可以根据「结果」来决定a 和b 的排序关系：
如果拼接结果ab 要比ba 好，那么我们会认为a 应该放在b 前面。

1
2
3
4
5
6
7
8
9
10
string largestNumber(vector<int>& nums) {
    vector<string> vs;
    for(auto x : nums) vs.push_back(to_string(x));
    sort(vs.begin(),vs.end(),[](const auto& A,const auto& B){
        return A + B > B + A;
    });
    string ans;
    for(const auto& x : vs) ans += x;
    return ans[0] == '0' ? "0" : ans; 
}

数字在升序数组中出现的次数

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

有序序列，就使用二分查找的思路。一开始的思路是先使用二分法找到k，然后从k开始向两边统计k的个数，但统计的这个时间复杂度达到了O(n)，导致整个算法的复杂度O(nlogn)，而通过两次二分查找，分别找到第一个k和最后一个k，可以使时间复杂度减少为O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
private:
    int findFirstK(const vector<int> &data, int k){
        int l = 0, r = data.size() - 1;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(data[mid] > k){
                r = mid - 1;
            } else if(data[mid] < k){
                l = mid + 1;
            } else if(mid - 1 >= 0 && data[mid - 1] == k){ // 左边还有相同的值，要继续往左边找
                r = mid - 1;
            } else{
                return mid;
            }
        }
        return -1;
    }
    int findLastK(const vector<int> &data, int k){
        int l = 0, r = data.size() - 1;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(data[mid] > k){
                r = mid - 1;
            } else if(data[mid] < k){
                l = mid + 1;
            } else if(mid + 1 < data.size() && data[mid + 1] == k){ // 右边还有相同的值，要继续往右边找
                l = mid + 1;
            } else{
                return mid;
            }
            mid = (l + r) >> 1;
        }
        return -1;
    }
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int first = findFirstK(data, k);
        int last = findLastK(data, k);
        if(first == -1 || last == -1){
            return 0;
        }
        return last - first + 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int GetNumberOfK(vector<int>& nums, int k) {
    // 分别查找k+0.5和k-0.5应该出现的位置，中间的部分就全是k
    // 不能查找k+1和k-1是因为，k+1和k-1也可能有多个，而k+0.5和k-0.5是不可能出现的
    // 2    3    6.5    `7`    7    7    `7.5`    8    9
    return bisearch(nums, k + 0.5) - bisearch(nums, k - 0.5);
}

// 当二分查找结束时，left 的值就是第一个大于或等于k 的元素的位置。
int bisearch(vector<int>& data, double k){
    int left = 0;
    int right = data.size() - 1;
    // 二分左右界
    while(left <= right){
        int mid = (left + right) / 2;
        if(data[mid] < k)
            left = mid + 1;
        else if(data[mid] > k)
            right = mid - 1;
    }
    return left;
}

不存在的正整数

在由整数组成的数组中，从小到大找出第一个不存在的正整数
用例1：
输入：[]
输出: [1]
用例2：
输入：[-4, 0, 4, 1]
输出：[2]
用例3：
输入：[-1, 0, 3, 1, 2, 25]
输出：[4]
用例4：
输入：[2, 1, 4, 3]
输出：[5]
用例5：
输入：[2, 2, 1, 4]
输出：[3]
用例6：
输入：[2, 1]
输出：[3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int getValue(vector<int>& v)
{
    int last = -1;
    int i = 0;
    for (i = 0; i < v.size();) {
        if (last > 0) {
            while (v[i] == last) i++;
            if (v[i] - last > 1) return v[i-1] + 1;
        }
        last = v[i];
        i++;
    }
    return v[i-1] + 1;
}

int main()
{
    vector<int> arr{2, 2, 1, 3, 4};
    sort(arr.begin(), arr.end());
    
    cout << getValue(arr) << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import "sort"

func getValue(v []int) int {
	last := -1
	for i, v := range v {
		if last > 0 {
			if i == last {
				continue
			}
			if v-last > 1 {
				return last + 1
			}
		}
		last = v
	}
	return last
}

func main() {
	a := []int{-1, 0, 3, 1, 2, 3, 25}
	sort.Ints(a)
	println(getValue(a))
}