#algorithm #data-structures
#алгоритм #структуры данных
Вопрос:
Вопрос для интервью: Дан массив, в котором любые два последовательных элемента отличаются по своим значениям на 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
Цель состоит в том, чтобы выполнить поиск элемента K в этом массиве менее чем за O (n).
Моя попытка: начать с индекса 0. мы можем пропустить некоторые индексы. Поскольку элементы отличаются на 1, и нам нужно выполнить поиск по k , позволяет найти элементы и увидеть диапазон, между которыми элемент может быть найден.
индекс = 0
Максимальное значение, которое я могу предсказать, будет равно [idx k], а минимальное значение — [idx -k], поскольку каждое значение отличается на 1 . однако это никуда не ведет
РЕДАКТИРОВАТЬ: Код, опробованный для предложения, приведенного в ответе
#include "stdafx.h"
#include "vector"
#include "iostream"
using namespace std;
int closeS(vector<int> amp; vec, int search , intamp; hopsTaken)
{
int idx = 0;
while (idx < vec.size() amp;amp; 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)
Комментарии:
1. Для поиска элемента можно использовать бинарный поиск.
2. Не будет работать, так как он будет подниматься и опускаться и иметь много локальных минимумов и максимумов
3. Будет несколько запросов или только один?
4. Невозможно. Допустим, у вас есть массив (0,1,0,1,…,0,1,2,1,0,…,1,0,1) и вам нужно выполнить поиск по 2. Вы не знаете, где в массиве находится это 2, и, возможно, не сможете узнать, не просмотрев по крайней мере N / 2 элементов.
5. @M.kazemAkhgary «это наихудший случай», я полагаю, также средний случай, буду рад увидеть контрпример. «я полагаю, что это может быть быстрее» Нет, наихудший случай не может быть быстрее. «очевидно, что многопоточный обман может ускорить работу», такого понятия, как «многопоточный обман», не существует. Если только у вас нет бесконечного числа процессоров, то есть. Если у вас 12 процессоров, O (n/ 12) по-прежнему равно O (n).
Ответ №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
Комментарии:
1. Какова временная сложность для вашего алгоритма?
2. это система … Не могли бы вы, пожалуйста, объяснить. Сложность, по-видимому, равна O (n / k)
3. Поскольку разница между элементами всегда равна 1, следующий индекс для проверки — это разница между k и текущим значением. Извините, я не могу определить сложность прямо сейчас, это был спонтанный пост, решающий проблему
4. Временная сложность равна O (n), например, если k = 4, а массив равен [2,1,2,1,2,1,2, …] -> алгоритм с переходом от 0, 2, 4, 6 … что равно n / 2 до конца массива.
5. Попробовал его подход в коде, который теперь является частью моего вопроса. Пробовал разные входные данные и, кажется, работает.. Пожалуйста, ваши входные данные .. как вы думаете, это будет принято на собеседовании?