Как сравнить каждый элемент в двух массивах с временной сложностью меньше, чем O (n ^ 2) - PullRequest
Новая
       9

Как сравнить каждый элемент в двух массивах с временной сложностью меньше, чем O (n ^ 2)

0 голосов
/ 03 ноября 2018

Предположим, у нас есть два массива A [n] и b [n], цель состоит в том, чтобы сравнить каждый элемент в A с элементами в B. Затем вернуть результат списка [n], который записывает номер каждого элемента в A, который больше, чем элементы в B.

Например,

A = [38, 24, 43, 3], B = [9, 82, 10, 11]

Так как 38 больше, чем 9, 10 и 11, поэтому результат [0] равен 3. Тогда результат будет [3, 3, 3, 0].

Будет лучше, если вы предоставите псевдокод.

Спасибо.

Ответы [ 2 ]

0 голосов
/ 04 ноября 2018

Вы можете выполнить вышеупомянутый алгоритм в сложности O (nlogn), где n - длина массива A и массива B, как указано в вопросе.

Алгоритм 

1. Sort both the arrays A and B, this will take O(nlogn) time complexity.
2. Take two pointers i and j, initialize both of them to 0. we will use i for array A and j for B.
3. Create a result array res of size n.
4. Start a while loop 
   while(i<n && j<n) {
     if(A[i] > B[j]) {
       j++;
     } else {
       res[i] = j+1;
       i++;
     }
   }
5. while(i<n) {
     res[i] = n;
   }
   This step is for the case where all elements in A are bigger than all elements in B.

В конце у вас будет готов массив res с ответом.

Общая сложность времени - O(nlogn).

Надеюсь, это поможет!

0 голосов
/ 04 ноября 2018

Оба списка должны быть отсортированы по возрастанию, чтобы это работало.

Расходы на сортировку O (log n) . А большая арифметика означает, что делать это дважды - все равно O(n log n). Я собираюсь предположить, что они уже отсортированы. Оставшаяся работа ниже не влияет на стоимость Big-O.

Иметь индекс для массива B с именем indexB, значение ноль (мой псевдокод будет использовать индексацию на основе нуля). И indexA для A, также начинающегося с нуля. 

indexA=0
For each indexB from 0 to B.Length-1
    While indexA < A.Length and the value at `A[indexA]` is less than or equal to the value at `B[indexB]`
        Set the `result[indexA]` to be `indexB`
        Increment `indexA`
    Endwhile
Endfor

После этого все остальные предметы в result начиная с indexA и далее больше, чем все предметы в B, поэтому установите остальные из них на B.Length.

...