Java Сравните три String-массива и используйте Binarysearch - PullRequest
Новая
       6

Java Сравните три String-массива и используйте Binarysearch

0 голосов
/ 05 февраля 2020

У меня есть три строковых массива длиной 9, и я хочу посмотреть, все ли они имеют одинаковые имена. Я должен сделать это в линеарифмическом c времени, O (NlogN). Мой план состоит в том, чтобы отсортировать два массива, а затем использовать двоичный поиск для поиска похожих имен. Мой код выглядит следующим образом: 

import edu.princeton.cs.algs4.*;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

public class Triplicate2_2_21 {

  // arrays.binarysearh
  public static void main(String[] args) {
    //Strengir sem innihalda 9 nöfn. Sumir innihalda sama nafnið.
    //Nöfn sem eru eins í öllum 3 listunum eru Hulda og Ingi.
    String[] name1 = {"Helgi", "Arnar", "Hulda", "Hrefna", "Ingi", "Marta",
                    "Svavar", "Ester", "Valur"};
    String[] name2 = {"Oddur", "Birgitta", "Hulda", "Ingi", "Selma", "Svavar",
                    "Sylvia", "Unnar", "Hrefna"};
    String[] name3 = {"Elfa", "Jan", "Hulda", "Hrund", "Ingi", "Marta",
                    "Angela", "Sturla", "Valur"};

    Arrays.sort(name2);
    Arrays.sort(name3);

    for(int i = 0; i < name1.length; i++) {
        if((Arrays.binarySearch(name2,name1[i])).compareTo(Arrays.binarySearch(name3,name1[i])) < 0 ) {
          StdOut.println(name1[i]);
          break;
        }}}}

Я просто хочу распечатать первый найденный мной триплет, поэтому я ломаюсь. Этот пример кода не работает, и я не могу понять, как реализовать эту идею дальше. Итак, я здесь, чтобы найти вашу помощь, чтобы закончить sh this.

Ps это домашнее задание, и вопрос из книги «Введение в алгоритмы», 4-е издание, и звучит так:

"Тройные копии. Учитывая три списка из N имен в каждом, разработайте алгоритм c linearithmi, чтобы определить, существует ли какое-либо имя, общее для всех трех списков, и, если да, вернуть первое".

1 Ответ

3 голосов
/ 05 февраля 2020

Arrays.binarySearch возвращает int, поэтому нет метода compareTo. Ваш код не компилируется.

Чтобы исправить это, измените условную часть следующим образом: 

if (Arrays.binarySearch(name2, name1[i]) > -1 && Arrays.binarySearch(name3, name1[i]) > -1) {
                System.out.println(name1[i]);
                break;
            }
        }

, чтобы поймать случай, когда оба поиска сигнализируют find.

...