Java: Finden Position der Elemente in einer Matrix von einem anderen Array

Question

Ich habe zwei Arrays:

a = [a1, a2, a3, a4, .., an] in aufsteigenden geordnet;

b = [b1, b2, b3, ..., bm] aufsteigend sortiert;

Ich möchte die Position der Elemente von Array b in Array kennen a.

Gibt es einen schnellen Weg, es zu tun, anstatt eins nach dem anderen zu finden?

Answer 1

Wie erwähnt Arrays sind sortiert, können Sie die binäre Suche durchführen.

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

Ich habe eingebaute Bibliothek für binäre Suche verwendet. Ich hoffe es hilft! Ich habe den Code aktualisiert.

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

    }