寒光博客

[CC150]9.3魔术索引 算法优化
魔术索引 在数组A[0..n-1]中,有所谓的魔术索引,满足条件A[i]=i。给定一个升序数组,元素值各不相同,编...
扫描右侧二维码阅读全文
08
2019/08

[CC150]9.3魔术索引 算法优化

魔术索引

在数组A[0..n-1]中,有所谓的魔术索引,满足条件A[i]=i。给定一个升序数组,元素值各不相同,编写一个方法,判断在数组A中是否存在魔术索引。请思考一种复杂度优于o(n)的方法。给定一个int数组A和int n代表数组大小,请返回一个bool,代表是否存在魔术索引。
测试样例:

[1,2,3,4,5] 返回:false
[1,2,3,4,5,6,6,8,9] 返回:true

分析

首先 题目说优于O(n) 所以只能在遍历优化
0~n - 1进行遍历,如果当前A[i] == i,返回true;如果A[i] < i, 则i ++;如果A[i] > i,则令i = A[i],即跳过A[i] - i个元素(因为序列是非递减的,所以A[i] > i时,至少到i = A[i]处,才有可能出现A[i] == i)。
例如2, 2, 2, 4, 5序列,i == 0时,A[i] = 2,则应跳过i = 1,直接比较i = 2处。

c[i] > i

如果下标小于值,那么实际上有:
下标i到下标A[i-1]的位置都不可能存在A[i]=i
因为下标i对应的A[i]已经大于A[i-1]了

当然也可以考虑使用二分法

代码

    private static boolean solve(int[] c) {
        for (int i = 0; i < c.length; ) {
            if (i == c[i])
                return true;
            else if (c[i] > i) {
                i = c[i];
            } else {
                i++;
            }
        }
        return false;
    }
本文作者:Author:     文章标题:[CC150]9.3魔术索引 算法优化
本文地址:https://dxoca.cn/Algorithm/228.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 9th, 2019 at 08:15 am
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment