LeetCode 1064. 不动点

Categories:

题目描述
思路分析
1. 解法一：二分查找左边界（推荐）
相似题目

题目描述

✅ 1064. 不动点

思路分析

解法一：二分查找左边界（推荐）

核心思路：

数组有序，寻找最小的 arr[i] == i。

使用二分查找，满足条件时继续向左收缩。

若不存在则返回 -1。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示数组长度。

空间复杂度：O(1)。

class Solution {
    public int fixedPoint(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        int ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == mid) {
                ans = mid;
                right = mid - 1;
            } else if (arr[mid] < mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

func fixedPoint(arr []int) int {
    left, right := 0, len(arr)-1
    ans := -1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == mid {
            ans = mid
            right = mid - 1
        } else if arr[mid] < mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return ans
}

相似题目

题目	难度	考察点
704. 二分查找	简单	二分
35. 搜索插入位置	简单	二分
278. 第一个错误的版本	简单	二分
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分
1064. 不动点	简单	二分

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/13171883