时间戳

首页 > 解决方案 > Java比较三个字符串数组并使用Binarysearch

java - Java比较三个字符串数组并使用Binarysearch

问题描述

我有三个长度为 9 的字符串数组，我想看看它们是否都包含相同的名称。我必须在线性时间 O(NlogN) 内完成此操作。我的计划是对两个数组进行排序，然后使用二进制搜索来查找相似的名称。我的代码是这样的ATM：

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;
        }}}}

我只想打印出我找到的第一个一式三份，这就是我打破的原因。这个代码示例不起作用，我无法弄清楚如何进一步实现这个想法。所以，我在这里寻求你的帮助来完成这个。

Ps 这是一个家庭作业，问题来自《算法导论》，第 4 版，听起来像这样：

“一式三份。给定三个列表，每个列表有 N 个名称，设计一个线性算法来确定所有三个列表是否有任何共同的名称，如果有，则返回第一个”。

标签： javaarraysstringalgorithmbinary-search

解决方案

Arrays.binarySearch确实返回一个int，因此没有compareTo方法。您的代码无法编译。

要修复它，请像这样更改条件部分：

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

捕获两个搜索都发出信号 a 的情况find。

推荐阅读