二分查找一＞0~n

1.题目： 

2.解析： 方法一：用哈希表：记录存在的数字，找到哈希表为空的数字输出

代码语言：javascript代码运行次数：0运行复制
Set<Integer> set = new HashSet<>();
        for(int x : records) set.add(x);

        for(int i = 0; i < set.size(); i++){
        if(!set.contains(i)) return i;
        }
        return set.size();

方法二：位运算异或 

代码语言：javascript代码运行次数：0运行复制
int ret = 0;
        for (int i = 0; i < records.length; i++) {
            ret ^= records[i];
            ret ^= i + 1;
        }

        return ret;

方法三：直接遍历

代码语言：javascript代码运行次数：0运行复制
int ret = 0;
        for(int i = 0; i < records.length; i++){
            if(records[i] != i) return i;
        }
        return records.length;

方法四：二分查找： 

注意：特殊情况整个数组元素及对应下标都一样时

代码语言：javascript代码运行次数：0运行复制
        int left = 0,right = records.length-1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(records[mid] == mid) left = mid+1;
            else right = mid;
        }
        
        //特殊情况：整个数组元素及对应下标都一样时
        return records[left] == left ? left+1 : left;
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-11，如有侵权请联系 cloudcommunity@tencent 删除intreturnset遍历数组