不动点

1064. 不动点

给定已经按升序排列、由不同整数组成的数组 arr，返回满足 arr[i] == i 的最小索引 i。如果不存在这样的 i，返回 -1。

示例 1：

输入：arr = [-10,-5,0,3,7]
输出：3
解释：对于给定的数组，arr[0] = -10，arr[1] = -5，arr[2] = 0，arr[3] = 3，因此输出为 3 。

示例 2：

输入：arr = [0,2,5,8,17]
输出：0
解释：arr[0] = 0，因此输出为 0 。

示例 3：

输入：arr = [-10,-5,3,4,7,9]
输出：-1
解释：不存在这样的 i 满足 arr[i] = i，因此输出为 -1 。

提示：

1 <= arr.length < 10⁴
-10⁹ <= arr[i] <= 10⁹

进阶：时间复杂度为 O(n) 的解决方案很直观也很简单。你可以设计更优的解决方案吗？

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int fixedPoint(vector<int>& arr) { } };

golang 解法, 执行用时: 4 ms, 内存消耗: 4.2 MB, 提交时间: 2023-10-15 19:01:11

func fixedPoint(A []int) int {
    i, j := 0, len(A)-1
    for i <= j {
        mid := i + (j-i)/2
        if A[mid] >= mid {
            j = mid-1
        } else {
            i = mid+1
        }
    }
    
    if i < len(A) && A[i] == i {
        return i
    } 
    
    return -1
}

golang 解法, 执行用时: 8 ms, 内存消耗: 4.2 MB, 提交时间: 2023-10-15 19:00:52

func fixedPoint(arr []int) int {
    l := 0
    r := len(arr)-1
    for l <= r {
        m := (l+r)/2
        if arr[m] == m {
            r = m-1
        } else if arr[m] > m {
            r = m-1
        } else {
            l = m+1
        }
    }
    if l < len(arr) && arr[l] == l {
        return l
    }
    return -1
}

python3 解法, 执行用时: 40 ms, 内存消耗: 17.1 MB, 提交时间: 2023-10-15 19:00:05

class Solution:
    def fixedPoint(self, arr: List[int]) -> int:
        n = len(arr)
        for i in range(n):
            if arr[i] == i:
                return i
        return -1

python3 解法, 执行用时: 36 ms, 内存消耗: 17.2 MB, 提交时间: 2023-10-15 18:59:53

class Solution:
    def fixedPoint(self, arr: List[int]) -> int:
        ##原数组升序，有序的情况可以考虑用二分优化
        ##二分法。框架----寻找符合（i <= arr[i]）的最左端
        n = len(arr)
        L = 0
        R = n-1
        while L < R:
            mid = (L + R) // 2
            if mid <= arr[mid]:
                R = mid     #去左边找
            else:
                L = mid + 1 #寻找符合条件的最左端 （标志性的句子）
        return L if arr[L]==L else -1

cpp 解法, 执行用时: 12 ms, 内存消耗: 10.8 MB, 提交时间: 2023-10-15 18:59:31

class Solution {
public:
    // 二分法
    int fixedPoint(vector<int>& arr) {
        int left = 0, right = arr.size() - 1, mid;
        while (left < right) {  // 有多个可能的解时，停在最左侧的位置
            mid = (left + right) >> 1;
            if (arr[mid] >= mid) {  // 有多个满足条件时，尽量向左侧移动
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left == arr[left] ? left : -1;
    }
};

python3 解法, 执行用时: 48 ms, 内存消耗: 17 MB, 提交时间: 2023-10-15 18:59:25

class Solution:
    def fixedPoint(self, arr: List[int]) -> int:
        return min((i  for i, num in enumerate(arr) if num == i), default=-1)

上一题

下一题

详情