Java : Taking 2 array find if the element that exists in both array return true if exist else false

Question

我正在寻找有关此解决方案的一些说明。谁能指导我以下两点:

1. 下面的算法是好的解决方案吗？
2. 我的 Big O 计算正确吗？

非常感谢您的澄清。提前致谢

public static void main(String[] args) {
    String[] a = {"a", "b", "c", "d"};
    String[] b = {"z", "f", "c"};

    boolean value1 = find(a, b);
    System.out.println(value1);

    boolean value2 = findArray(a, b);
    System.out.println(value2);

}

/*
since the both the array is of diff size for nested loop
Big O  = O(n*n)
if array size is same Big O = O(n^2)
 */
private static boolean find(String[] a, String[] b) {
    for (int i = 0; i < a.length; i++) {
        String val1 = a[i];
        for (int j = 0; j < b.length; j++) {
            if (val1.equals(b[j])) {
                System.out.println(val1 + " : " + b[j]);

                return true;
            }
        }// O(n)
    }// O(n)
    return false;
}// O(n*n)

/*
Big O  = O(n)
 */
private static boolean findArray(String[] a, String[] b) {
    //create array list from array
    List<String> list = new ArrayList<>(Arrays.asList(b));
    for (int i = 0; i < a.length; i++) {
        String val1 = a[i]; //O(1)

        if (list.contains(val1)) {
            System.out.println(val1 + " : contain in list b");
            return true;
        }// O(1)

    }// O(n)
    return false;
}// O(n)

Answer 1

你的第二个解决方案也是 O(N^2)，因为 contains 的工作原理是 O(N)。

第一个解决方案 O(N*LogN):

1. 对第二个数组进行排序。 NLogN
2. 迭代第一个 O(N) 和 binary search通过第二个1 O(logN) => O(NLogN)

总体复杂度 O(NLogN)

第二个解决方案 O(N) - 如果数组已排序。如果不是 O(NLogN)，因为步骤 1

1. 对两个数组进行排序 O(NlogN)
2. 做这样的事情

代码:

int curA = 0, curB = 0;
while (true) {
 if (curA >= a.length || curB >= b.length)
  break;
 if (a[curA] < b[curB]) {
  curA++;
  continue;
 }

 if (a[curA] > b[curB]) {
  curB++;
  continue;
 }

 return true;
}
return false;