Каков быстрый способ получить индекс элемента в массиве?

Ответ 1

Пока нет сведений о массиве (сортируется ли оно по возрастанию или по убыванию? и т.д.), нет способа найти элемент без проверки каждого из них.

Кроме того, это именно то, что делает indexOf (при использовании списков).

Ответ 2

Как найти индекс элемента, имеющего значение X в массиве?

Это будет быстро:

int getXIndex(int x){
    myArray[0] = x;
    return 0;
}

Ответ 3

Практический способ найти его быстрее - это параллельная обработка.

Просто разделите массив в N частях и назначьте каждую часть потоку, который выполняет итерацию через элементы своей части до тех пор, пока не будет найдено значение. N предпочтительно должен быть числом процессоров ядер.

Ответ 4

Если двоичный поиск невозможен (beacuse массив не сортируется), и у вас нет какого-либо индекса расширенного поиска, единственный способ, которым я мог бы думать, это не O(n), если позиция элемента в массиве является функцией самого элемента (например, если массив [10, 20, 30, 40], позиция элемента n равна (n / 10) - 1).

Ответ 5

Возможно, он хочет проверить ваши знания о Java.

Существует класс Utility под названием Arrays, этот класс содержит различные методы манипуляции массивами (например, сортировка и поиск)

http://download.oracle.com/javase/6/docs/api/java/util/Arrays.html

В 2 строках вы можете получить результат O (n * log n):

    Arrays.sort(list); //O(n * log n)
    Arrays.binarySearch(list, 88)); //O(log n)

Ответ 6

Использование квантового компьютера:

http://en.wikipedia.org/wiki/Grover%27s_algorithm

Ответ 7

Puneet - in.net его:

string[] testArray = {"fred", "bill"};
var indexOffset = Array.IndexOf(testArray, "fred");

[edit] - прочитав вопрос правильно,:) альтернативой в linq будет:

string[] testArray = { "cat", "dog", "banana", "orange" };
int firstItem = testArray.Select((item, index) => new
{
    ItemName = item,
    Position = index

}).Where(i => i.ItemName == "banana")
  .First()
  .Position;

это, конечно, обнаружит ПЕРВОЕ появление строки. последующие дубликаты потребуют дополнительной логики. но тогда также был бы замкнутый подход.

джим

Ответ 8

Это вопрос о структурах данных и алгоритмах (хотя и очень простая структура данных). Он выходит за пределы используемого вами языка.

Если массив упорядочен, вы можете получить O (log n), используя двоичный поиск и модифицированную версию его для пограничных случаев (не используя всегда (a + b)/2 как опорную точку, но это довольно сложная причуда).

Если массив не упорядочен, то... удачи.

Он может расспрашивать вас о том, какие методы у вас есть, чтобы найти элемент на Java. Но в любом случае они не быстрее. Они могут быть проще использовать (чем для каждого - сравнивать - возвращать).

Другое решение, создающее вспомогательную структуру для более быстрого поиска (например, hashmap), но из-за COURSE, более дорогое создание и использование его один раз, чем простой линейный поиск.

Ответ 9

Возьмите совершенно несортированный массив, просто список чисел в памяти. Все, что может сделать машина, - это посмотреть на отдельные цифры в памяти и проверить, являются ли они правильным числом. Это "проблема с взломом паролей". Существует не более быстрый способ, чем поиск с самого начала, пока не будет достигнуто правильное значение.

Ответ 10

Вы уверены в вопросе? У меня есть вопросы, похожие на ваш вопрос.

Для отсортированного массива существует один элемент "x", значение которого совпадает с его индексом, нахождение индекса этого элемента.

Например:

         //0,1,2,3,4,5,6,7,8,9, 10     
int a[10]={1,3,5,5,6,6,6,8,9,10,11};

в индексе 6, что значение и индекс одинаковы.

для этого массива a, ответ должен быть 6.

Это не ответ, если в исходном вопросе что-то пропустило, это прояснит это.

Ответ 11

Если единственная информация, которую вы имеете, это тот факт, что это несортированный массив без перераспределения между индексом и значением и без каких-либо вспомогательных структур данных, тогда вы должны потенциально изучить каждый элемент, чтобы узнать, содержит ли он информацию, которую вы хотите.

Однако интервью предназначены для ветки пшеницы от мякины, поэтому важно понять, что они хотят видеть, как вы приближаетесь к проблемам. Поэтому идея состоит в том, чтобы задавать вопросы, чтобы узнать, доступна ли (или может быть сделана) информация, которая может сделать ваш поиск более эффективным.

Вопросы вроде:

1/Часто ли данные меняются?

Если нет, вы можете использовать дополнительную структуру данных.

Например, поддерживайте флаг dirty, который изначально имеет значение true. Когда вы хотите найти элемент, и это правда, создайте дополнительную структуру (отсортированный массив, дерево, хеш или что-то еще), что значительно ускорит поиск, а затем установите флаг dirty в значение false, затем используйте эту структуру, чтобы найти элемент.

Если вы хотите найти элемент, а флаг dirty - false, просто используйте структуру, нет необходимости перестраивать ее.

Конечно, любые изменения в данных должны устанавливать флаг dirty равным true, чтобы следующий поиск перестраивал структуру.

Это значительно ускорит (через амортизацию) запросы для данных, которые читаются гораздо чаще, чем написано.

Другими словами, первый поиск после изменения будет относительно медленным, но последующий поиск может быть намного быстрее.

Возможно, вам захочется обернуть массив внутри класса, чтобы вы могли правильно управлять флагом dirty.

2/Разрешено ли использование другой структуры данных, чем исходный массив?

Это будет похоже на первую точку, указанную выше. Если мы изменим структуру данных из массива на произвольный класс, содержащий массив, вы все равно сможете получить все преимущества, такие как быстрый произвольный доступ к каждому элементу.

Но мы получаем возможность обновлять дополнительную информацию в структуре данных всякий раз, когда данные изменяются.

Итак, вместо использования флага dirty и выполнения большого обновления при следующем поиске мы можем внести небольшие изменения в дополнительную информацию всякий раз, когда изменяется массив.

Это избавляет от медленного ответа первого поиска после изменения, амортизируя стоимость всех изменений (каждое изменение имеет небольшую стоимость).

3. Сколько элементов обычно будет в списке?

Это действительно более важно, чем большинство людей понимают.

Все разговоры об оптимизации, как правило, бесполезны, если ваши наборы данных не являются относительно большими, а производительность действительно важна.

Например, если у вас есть массив из 100 предметов, вполне приемлемо использовать даже мозговую мертвую форму пузыря, поскольку разница в таймингах между тем и самым быстрым видом, который вы можете найти, как правило, не имеет значения (если вам не нужно делайте это тысячи раз в секунду, конечно).

В этом случае, найдя первый индекс для данного значения, вероятно, вполне приемлемым для последовательного поиска, если ваш массив остается под определенным размером.

Суть в том, что вы там, чтобы доказать свою ценность, и интервьюер (как правило) там, чтобы вести вас. Если они не садисты, они вполне счастливы, если вы зададите им вопросы, чтобы попытаться сузить область проблемы.

Задайте вопросы (как у вас есть возможность для сортировки данных). Они должны быть впечатлены вашим подходом, даже если вы не можете найти решение.

Фактически (и я делал это в прошлом), они могут отклонить все ваши возможные подходы (нет, они не отсортированы, нет, никаких других структур данных не разрешены и т.д.), чтобы увидеть, насколько далеко вы получить.

И, может быть, просто, может быть, как Кобаяси Мару, возможно, это не победа, может быть, как вы справляетесь с провалом: -)