Как сканировать ArrayList на длину строки - PullRequest
Новая
       29

Как сканировать ArrayList на длину строки

1 голос
/ 25 июня 2019

У меня есть ArrayList строк, отсортированных по длине. Мне нужно сравнить строки, которые имеют одинаковую длину.

Например, гипотетический список:

["my", "by", "he", "she", "sun", "car"]

Мне нужно сравнить "my" только с "by" и "he", "she" только с "sun" и "car".

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

for(int i = 0; i<strings.size()-1; i++) {
  for (int j = i+1; j<strings.size();j++) {
    System.out.println(strings.get(i).compareTo(strings.get(j)));     
  }
}

Ответы [ 4 ]

1 голос
/ 25 июня 2019

Огромное преимущество здесь в том, что список уже отсортирован по возрастанию.А если это не так, то сначала просто отсортируйте его по длине, а затем примените операцию, которую вы хотите здесь.Или, если вы не хотите сортировать по длине, в приведенном ниже примере измените значение break на continue.

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

for(int i = 0; i<strings.size()-1; i++) {
  for (int j = i+1; j<strings.size(); j++) {
    if (strings.get(i).length() != strings.get(j).length()) break;
    System.out.println(strings.get(i).compareTo(strings.get(j)));   
  }
}

Обратите внимание, это будет работать независимо от того, отсортирован ли список по возрастанию или уменьшению.

1 голос
/ 25 июня 2019

Вы также можете создавать сегменты на основе определенного свойства, используя Collectors#partitioningBy API Java Stream. 

Map<Integer, List<String>> map = yourList.stream()
    .collect(Collectors.partitioningBy(String::length));

Затем вы можете обработать каждый сегмент, указав размер: 

int length = 3;
List<String> bucket = map.get(length);
1 голос
/ 25 июня 2019

Вы можете добавить проверку длины строки: 

for (int i = 0; i < strings.size() - 1; i++) {
    String a = strings.get(i);
    for (int j = i + 1; j < strings.size(); j++) {
        String b = strings.get(j);
        if (a.length() == b.length()) {
            System.out.println(a.compareTo(b));
        }     
    }
}
0 голосов
/ 26 июня 2019

Вы можете просто сначала разбить список на группы / разделы строк одинаковой длины. Создав группы / разделы, вы можете просто запустить приведенный выше код. В этом случае наихудшая временная сложность все еще остается O (n ^ 2), но в других сценариях она улучшается. В лучшем случае это будет O (n). Ниже код даст представление о том, что я говорю. Я использую метод groupingBy из Java Streams API. 

List<String> list = new ArrayList<>();

list.add("me");
list.add("by");
list.add("he");
list.add("she");
list.add("sun");
list.add("car");

Map<Integer, List<String>> mapOfSameLengthStrings = list
            .stream()
            .collect(Collectors.groupingBy(String::length));

for (Map.Entry<Integer,List<String>> entry : mapOfSameLengthStrings.entrySet()) {
    List<String> listOfSameLengthStrings = entry.getValue();
    for(int i = 0; i<listOfSameLengthStrings.size()-1; i++) {
        for (int j = i+1; j<listOfSameLengthStrings.size();j++) {
                System.out.println(listOfSameLengthStrings.get(i).compareTo(listOfSameLengthStrings.get(j)));
        }
    }
}

Вывод вышеуказанного кода ниже: 

11
5
-6
-13
16
16

Это делает 6 сравнений, это то, что вам нужно согласно моему пониманию вашего запроса Надеюсь, это помогло.

...