Java：从另一个数组中查找一个数组中元素的位置

Question

我有两个数组：

a = [a1,a2,a3,a4,..,an] 升序排列；

b = [b1,b2,b3,...,bm] 升序排列；

我想知道数组b的元素在数组a中的位置

有没有不用一个一个找的快速的方法？

Answer 1

提到数组是有序的，可以进行二分查找

import java.util.Arrays;

class ArrayTest {
    public static void main(String[] args) {
        int a[] = { 1, 2, 5, 7 };
        int b[] = { -2, 2, 3, 4, 5, 6 };
        for (int i = 0; i < b.length; i++) {
            int position = Arrays.binarySearch(a, b[i]);
            if (position >= 0)
                System.out.println("Element " + b[i] + " is at " + position
                        + " in array A");
            else {
                // System.out.println("Element does not exist in array A");
                int lower = -1;
                int upper = -1;
                for (int j = 0; j < a.length; j++) {
                    if (b[i] > a[j]) {
                        lower = j;
                    } else {
                        upper = j;
                    }
                    if (upper != -1)
                        break;
                }
                if (upper <= 0)
                    System.out.println("Element " + b[i] + " is at before 0");
                else
                    System.out.println("Element " + b[i] + " is Between "
                            + lower + " and " + upper);
            }
        }
    }
}

我已经使用 in-built 库进行二进制搜索。希望能帮助到你！我更新了代码。

Answer 2

O(m)+O(n)

    //assuming both a and b are sorted in ascending order
    int startA = 0, startB = 0;
    int[] a = {2,4,6,8,9};
    int[] b = {1,4,9};
    int[] result = new int[b.length];
    //result[i] suggest position of ith element of array b in array a. you can initialize all elements of result to -1 indicating not present in a
    int endB = b.length, endA = a.length;
    while(startB<endB && startA<endA){
        if(b[startB]<a[startA]){
            startB++;
        }
        else if(b[startB]>a[startA]){
            startA++;
        }
        else{
            result[startB]=startA;
            startB++;
        }

    }

Java：从另一个数组中查找一个数组中元素的位置

Java: Find position of elements in an array from another array

java

algorithm

indexing

position