arrays - 查找相同的数组下标和值

Question

我有一个 n 元素的排序数组。这些值可以是负数或正数。

该数组的特点是在 n 个元素中，有 1 个特定元素的 a[x]=x 且其余数据不满足条件。

除了循环整个数组之外，还有什么更好的方法可以找到这样的“x”。

假设我的数组是 [-2999,-33,0,2,4,67,654] 这里 a[4]=4 其余的不符合这样的标准..

score 1 · Accepted Answer

由于数组已经排序，您可以使用 O(lgn) 的二进制搜索来查找元素。

您也可以忽略所有负值元素，因为索引不能为负。

score 0 · Accepted Answer

你可以用这个。这是 O(N)。

for(i=0;i<MAX;i++){
    if(i==array[i]){//do something}
}

如果数组按降序排序，请使用

for(i=MAX-1;i>=0;i11){
    if(i==array[i]){//do something}
}

这里 MAX 是数组的大小

2 回答 2