Есть ли метод поиска лучше, чем O (n) для ArrayList? - PullRequest
Новая
       17

Есть ли метод поиска лучше, чем O (n) для ArrayList?

0 голосов
/ 31 августа 2018

У меня вопрос из викторины: 

If input data of randomList are 4 5 1 2 3 4
Results are:
pick(4) -> 4 4
pick(1) -> 1
pick(2) -> 2
pick(6) -> there is no value

Это коды по умолчанию, и мы можем разместить любые коды в любом месте: 

public static void main(String[] args){
    List<Integer> randomList = new ArrayList<>();
    for(int i = 0; i < 100000000; i++) {
        randomList.add(new Random().nextInt());
    }
    .....
    System.out.println("result = " + pick(new Random().nextInt()));

Вопрос в том, что является наиболее эффективным методом для функции pick (), который лучше, чем O (n)?

Это моя версия O (n): 

static List<Integer> list2 = new ArrayList<>();

public static void main(String[] args){
    List<Integer> randomList = new ArrayList<>();
    for(int i = 0; i < 10; i++) {
        randomList.add(new Random().nextInt(5)+1);
    }

    list2 = randomList;

    System.out.println("result = " + pick(new Random().nextInt(5)+1));
}

public static String pick(int rand) {
   String result = "";
   System.out.println("search = " + rand);

   for(Integer s : list2) {
        if(s == rand) {
            result = result + " " + rand;
        }
    }
   return result;
}

Большое спасибо.

Ответы [ 2 ]

0 голосов
/ 31 августа 2018

Учитывая ваши ограничения, нет лучшего алгоритма поиска, кроме O (n). Причина этого:

  • Ваши данные содержат «рандомизированные» значения от 0 до 100 000 000
  • Вы хотите собрать все значения, которые соответствуют заданному числу (в вашем примере 4)
  • У вас нет возможности отсортировать список (что потребует дополнительных затрат O (n * log (n)))

Единственный способ, которым это могло бы стать лучше, - это если бы вы могли переместить свой набор данных в другую структуру данных, такую ​​как Карта. Тогда за загрузку данных вы понесли бы штраф O (n), но после этого вы сможете найти значения в постоянном времени.

0 голосов
/ 31 августа 2018

Если вы используете Map, в котором ключ является вашим входным значением, а значение является частотой, тогда Map найдет ключ во O(1) времени. Построение строки будет пропорционально частоте нажатия клавиши. Итак, код может быть следующим: 

Map<Integer, Integer> mapList = new HashMap<>();
public static void main(String[] args){
    for(int i = 0; i < 10; i++) {
        int key = new Random().nextInt(5)+1;
        if (mapList.contains(key)) {
            mapList.put(key, mapList.get(key) + 1);
        } else {
            mapList.put(key, 1);
        } 
    }

    System.out.println("result = " + pick(new Random().nextInt(5)+1));
}

public static String pick(int rand) {
    Integer count = mapList.get(rand);
    if (count == null) {
        return "";
    } 
    StringJoiner sj = new StringJoiner(" ");
    for (int i = 0; i < count; i++) {
        sj.add(rand);
    }
    return sj.toString();
}

Редактировать

Как подсказывает @Pshemo, вместо StringBuilder используется StringJoiner, так как он более компактен и не добавляет лишнего пробела для последнего символа.

...