Как проверить есть ли элемент в массиве java
Перейти к содержимому

Как проверить есть ли элемент в массиве java

  • автор:

Проверка наличия элемента в массиве строк

Является ли этот метод оптимальным, или же это «велосипед», и существует более оптимальное решение этой задачи?

Отслеживать
19.1k 6 6 золотых знаков 30 30 серебряных знаков 44 44 бронзовых знака
задан 13 янв 2017 в 22:09
513 1 1 золотой знак 5 5 серебряных знаков 19 19 бронзовых знаков
Массив сортирован? Можно ли его отсортировать?
13 янв 2017 в 22:21
Массив не отсортирован, порядок его элементов не имеет значения
14 янв 2017 в 14:06
Юзайте, то что написали, это нормальное решение, для массива из <= 15 элементов. 14 янв 2017 в 19:03

4 ответа 4

Сортировка: Сброс на вариант по умолчанию

Если не касаться вопроса сортировки, то более короткой формой будет

return Arrays.asList(massStringA).contains(s); 

(заметьте, Arrays.asList() не создаёт копию массива, а использует оригинал, так что это не удваивает расход памяти).

Отслеживать
ответ дан 13 янв 2017 в 22:31
2,181 15 15 серебряных знаков 21 21 бронзовый знак

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

String[] massStringA = . ; // массив будет изменен! Arrays.sort(massStringA); if(Arrays.binarySearch(massStringA, a) >= 0) < // строка найдена >; 

Если массив нельзя изменять и используется Java 8, то можно применить Stream

if(Arrays.stream(massStringA).anyMatch(s -> s.equals(a))) < // строка найдена >

Отслеживать
ответ дан 13 янв 2017 в 23:54
Mikhail Vaysman Mikhail Vaysman
14.2k 1 1 золотой знак 21 21 серебряный знак 31 31 бронзовый знак

Более оптимальное решение — скопировать String[] в HashSet , после чего использовать метод contains у HashSet .

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

private static final int STRINGS_COUNT = 100 * 1000, TESTS_COUNT = 100 * 1000; private static final HashSet hashSet = new HashSet<>(); private static final String[] massStringA = new String[STRINGS_COUNT]; public static void main(String[] args) < for (int i = 0; i < STRINGS_COUNT; i++) < massStringA[i] = createString(i); >long startTime = System.currentTimeMillis(); hashSet.addAll(Arrays.asList(massStringA)); System.out.println("Copy time: " + (System.currentTimeMillis() - startTime) + "ms"); Random rand = new Random(); String[] testStrings = new String[TESTS_COUNT]; for (int i = 0; i < TESTS_COUNT; i++) < int randValue = rand.nextInt(STRINGS_COUNT * 10); testStrings[i] = createString(randValue); >startTime = System.currentTimeMillis(); int matches = 0; for (int i = 0; i < TESTS_COUNT; i++) < if (existA(testStrings[i])) < matches++; >> System.out.println("Array search time: " + (System.currentTimeMillis() - startTime) + "ms, matches: " + matches); startTime = System.currentTimeMillis(); matches = 0; for (int i = 0; i < TESTS_COUNT; i++) < if (Arrays.asList(massStringA).contains(testStrings[i])) < matches++; >> System.out.println("Arrays.asList search time: " + (System.currentTimeMillis() - startTime) + "ms, matches: " + matches); startTime = System.currentTimeMillis(); matches = 0; for (int i = 0; i < TESTS_COUNT; i++) < if (hashSet.contains(testStrings[i])) < matches++; >> System.out.println("HashSet search time: " + (System.currentTimeMillis() - startTime) + "ms, matches: " + matches); > private static String createString(int number) < int value = number; StringBuilder sb = new StringBuilder(); while (value >0) < sb.append((char)(value % 80 + 47)); value /= 80; >return sb.toString(); > private static boolean existA(String a) < for (String s : massStringA) < if (a.equals(s)) < return true; >> return false; > 

Для 100 тысяч тестов при 100 тысячах строк результаты такие:

Copy time: 16ms Array search time: 69762ms, matches: 9858 Arrays.asList search time: 73248ms, matches: 9858 HashSet search time: 14ms, matches: 9858 

Для миллиона тестов при 10 тысячах строк:

Copy time: 3ms Array search time: 17775ms, matches: 99845 Arrays.asList search time: 17537ms, matches: 99845 HashSet search time: 26ms, matches: 99845 

Поиск элемента в массиве

Достаточно частая задача — это поиск элемента в массиве. Допустим у нас есть массив 1,5,8,10,16,20. 100 и нам нужно найти позицию элемента 10 в нем. Или вообще выяснить есть ли такой элемент в массиве.

Существуют следующие алгоритмы решающие эту задачу —

  • Линейный поиск — О(n)
  • Двоичный поиск — O(log (N))
  • Поиск прыжками — O(sqrt (N))
  • Интерполяционный поиск — O(log log N)
  • Экспоненциальный поиск — O(log (N))

Рассмотрим некоторые из них.

1. Линейный поиск

Самый простой, но и самый долгий алгоритм. Перебираем элементы массива и сравниваем с elementToSearch, который мы должны найти.

 public static int linearSearch(int[] array, int elementToSearch) < for (int i = 0; i < array.length; i++) < if (array[i] == elementToSearch) < return i; >> return -1; >

2. Двоичный поиск, итеративный подход

Для использования алгоритма, массив должен быть отсортирован. Идея метода состоит в том, что мы делим массив пополам, берем «средний элемент» с индексом middleIndex, и сравниваем с искомым. Если они равны, мы заканчиваем поиск. Если искомый элемент меньше «среднего элемента» мы отбрасываем правую часть массива, иначе — левую. После чего повторяем эти операции снова и снова, пока искомый элемент не будет найден, или пока новый отрезок не станет пустым. Если элемент не нашелся возвращаем значение -1.

public static int binarySearch(int[] array, int elementToSearch) < int firstIndex = 0; int lastIndex = array.length - 1; // условие прекращения (элемент не представлен) while (firstIndex // если средний элемент меньше // направляем наш индекс в middle+1, убирая первую часть из рассмотрения else if (array[middleIndex] < elementToSearch) < firstIndex = middleIndex + 1; >// если средний элемент больше // направляем наш индекс в middle-1, убирая вторую часть из рассмотрения else if (array[middleIndex] > elementToSearch) < lastIndex = middleIndex - 1; >> return -1; >

3. Двоичный поиск, рекурсивный подход

 public static int recursiveBinarySearch(int[] array, int firstElement, int lastElement, int elementToSearch) < // условие прекращения if (lastElement >= firstElement) < int middle = (lastElement + firstElement) / 2; // если средний элемент - целевой элемент, вернуть его индекс if (array[middle] == elementToSearch) < return middle; >// если средний элемент больше целевого // вызываем метод рекурсивно по суженным данным if (array[middle] > elementToSearch) < return recursiveBinarySearch(array, firstElement, middle - 1, elementToSearch); >// также, вызываем метод рекурсивно по суженным данным return recursiveBinarySearch(array, middle + 1, lastElement, elementToSearch); > return -1; >

4. Поиск прыжками

 public static int jumpSearch(int[] array, int elementToSearch) < int arrayLength = array.length; int jumpStep = (int) Math.sqrt(array.length); int previousStep = 0; while (array[Math.min(jumpStep, arrayLength) - 1] < elementToSearch) < previousStep = jumpStep; jumpStep += (int) (Math.sqrt(arrayLength)); if (previousStep >= arrayLength) < return -1; >> while (array[previousStep] < elementToSearch) < previousStep++; if (previousStep == Math.min(jumpStep, arrayLength)) < return -1; >> if (array[previousStep] == elementToSearch) < return previousStep; >return -1; >
  • Среднее арифметическое
  • Числа Фибоначчи
  • Вычисление сложности алгоритма
  • Метод swap
  • Реверс массива
  • Алгоритм сортировки пузырьком
  • Сортировка выбором
  • Задания

Как найти число в массиве java

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

Пример кода для поиска числа в массиве:

public static int findNumberInArray(int[] array, int number)  for (int i = 0; i  array.length; i++)  if (array[i] == number)  return i; // возвращаем индекс элемента, если он найден > > return -1; // возвращаем -1, если элемент не найден > 

Как найти индекс элемента в массиве java

Для Ивана Полежаева: а что, у класса Arrays есть такой метод? где почитать? Здесь ( https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html ) что-то не нашла. у ArrayList вижу.

05 апреля 2023

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

Вот пример кода:

public static int findIndex(int[] arr, int element)  for (int i = 0; i  arr.length; i++)  if (arr[i] == element)  return i; > > return -1; // если элемент не найден > 

06 апреля 2023

Для того, чтобы найти индекс элемента в массиве в Java , можно использовать метод indexOf класса java.util.Arrays Этот метод принимает на вход массив и искомый элемент, и возвращает индекс первого вхождения элемента в массиве. Если элемент не найден, метод возвращает -1.

Например, чтобы найти индекс числа 42 в массиве numbers , можно написать следующий код:

int[] numbers = 10, 20, 30, 40, 42, 50>; int index = Arrays.indexOf(myArray, 42); // 4 

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *