在数组中搜索元素相差1

Question

面试问题：给定一个数组，其中任何两个连续元素的值相差1

例：

vector<int> vec = { 1, 0, -1, -2, -3, -4,-3,-2,-1,0,1, 2, 1, 2, 3 };
            index==>0, 1,  2,  3,  4,  5, 6, 7, 8,9,10,11,12,13,14

目的是在小于O（n）的范围内搜索该数组中的元素K.

我的尝试：从索引0开始。我们可以跳过一些索引。由于元素相差1，我们需要搜索k，让昆虫元素看到可以找到哪个元素之间的范围。

index = 0

我可以预测的最大值将是[idx + k]和[idx -k]的最小值，因为每个值相差1 ..但是，这不会导致任何地方

编辑：代码尝试在答案中给出的建议

#include "stdafx.h"
#include "vector"
#include "iostream"
using namespace std;
int closeS(vector<int> & vec, int search , int& hopsTaken)
{
    int idx = 0;
    while (idx < vec.size() && vec[idx] != search)
    {
        idx += abs (search - vec[idx]);

        ++hopsTaken;
    }

    if (idx < vec.size())
    {
        cout << idx <<"\n";
        return idx;
    }

    return -1;
}

int main()
{
    int hopsTaken = 0;
    vector<int> vec = { 1,0,-1,-2,-3,-4,-3,-2,-1,0,1,2,1,2,3 };
    cout << closeS(vec, 3, hopsTaken);  // , 0, vec.size() - 1)];
    cout << "  \n hopsTaken " << hopsTaken <<"  in array size" << vec.size() <<" for k = " << 3 <<"\n";
    int y;
    cin >> y;

    return 0;
}

尝试了几件物品，总是<= O（n / k）

仍然寻找更好的仍然是O（n）

Answer 1

从第一个索引开始，然后按差异跳转到搜索到的元素：

例如搜索2：从索引0开始

0, vec[0]=1,  2-1=1  => nextindex 0+1=1
1, vec[1]=0,  2-0=2  => 1+2=3
3, vec[3]=-2, 2--2=4 => 3+4=7
7, vec[7]=-2, 2--2=4 => 7+4=11
11, vec[11]=2

例如，搜索3：从索引0开始

0, vec[0]=1,  3-1=2  => 0+2=2
2, vec[2]=-1, 3--1=4 => 2+4=6
6, vec[6]=-3, 3--3=6 => 6+6=12
12, vec[12]=1, 3-1=2  => 12+2=14
14, vec[11]=3