二分查找一＞0~n

admin管理员组

文章数量:1794759

二分查找一＞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遍历数组

本文标签： 二分查找一＞0n