Java: положение элементов в массиве из другого массива

Question

У меня есть два массива:

а = [a1, a2, a3, a4, .., ап] упорядочены по возрастанию;

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

Я использовал встроенную библиотеку для бинарного поиска. Надеюсь, поможет! Я обновил код.

Answer 2

O (м) + О (п)

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

    }