爪哇：查找從另一個數組的數組元素的位置

Question

我有兩個陣列：

A = [A1，A2，A3，A4，...，一個]有序的升序;

b = [b1，b2，b3，...，bm]按升序排列;我想知道數組a中的數組b的元素的位置。

有沒有一個快速的方法來做到而不是一個一個找？

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

我已經使用二進制搜索的內置庫。希望能幫助到你！ 我已經更新了代碼。

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

    }