Поиск наиболее частой строки в отсортированном ArrayList без использования HashMap - PullRequest
Новая
       6

Поиск наиболее частой строки в отсортированном ArrayList без использования HashMap

0 голосов
/ 09 декабря 2018

Учитывая ArrayList из String, содержащих 

animalsArray[dog, cat, dog, dog, cat, duck, duck, dog]

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

Если ArrayList был отсортирован 

[dog, dog, dog, dog, cat, cat, duck, duck]

Какой самый простой способ найти наиболее распространенный элемент без использования Hashmaps?Я думал об использовании цикла for, сравнивающего animalArray.get(i) с animalArray.get(i-1), но я не смог разработать это решение.И каковы преимущества, если таковые имеются, наличия сортировки ArrayList, когда нам нужно, нам нужно найти наиболее распространенный элемент?

1 Ответ

0 голосов
/ 09 декабря 2018

Какой самый простой способ найти наиболее распространенный элемент без использования хэш-карт?

Я бы посчитал (Java 8+) это довольно простым: 

String str = list.stream()
                 .distinct()
                 .max(Comparator.comparing(e -> Collections.frequency(list, e)))
                 .get();

, который создаст Stream из List и найдет элемент с наибольшей частотой в List.

И каковы преимущества, если они есть, наличия отсортированного ArrayList, когда нам нужно найти наиболее распространенный элемент?

Представьте себе несортированный List: 

[dog, cat, turtle, cat, dog, snake]

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

Однако с отсортированным List: 

[dog, dog, cat, cat, snake, turtle]

У вас должен быть только счетчик для отслеживания самого длинного подсписка, который содержит те же элементы.Тогда это превращается в нечто вроде (psuedocode): 

//T being the type of the List
T element
int count = 0;
int biggestCount = 0;
for(every element in the list) {
   if the item is the same as previous
      count++
   else 
      //Only check when we're about to change elements
      if count > biggestCount
          biggestCount = count
          element = current element of List
      //Starting over with a new element
      count = 1
}
return element
...