Member 13791698 Ответов: 1

Как скоординировать два массива вместе?

у меня есть массив A, который имеет разные n чисел, и еще один пустой массив B с такой же длиной n .
теперь мне нужно перейти к массиву A и в каждом элементе массива A[i] нам нужно
чтобы найти элемент , который ближе всего к A[i] слева и меньше A[i], а индекс найденного элемента мы помещаем в B[i], если такого элемента нет, то B[i]=-1.
например, для массива:
A:   3  7  10  2  10  9

B:  -1  0   1 -1  3   3


теперь проблема в том , что мне нужно написать код c для этого, но в O(n)времени и месте O(n) также ,
я не могу придумать, как это сделать с O(n), я могу сделать это только O(n^2)
есть какой-нибудь намек на то, как я могу сделать это всего за O(n) ?

Что я уже пробовал:

B[0]=-1;
for(i=1;i<n;i++){ 
  for(j=(i-1);j>=0;j--){
    if(A[j] < A[i]){
      B[i]=j;
      break;
    }
    if(j=0){
     B[i]=-1;
    }
  }
}

Mohibur Rashid

Ваш вопрос недостаточно ясен. Каков будет результат?

Member 13791698

массив B , например, посмотрите на A[5]=9, я смотрю слева на то , какой элемент меньше 9 , начиная с 10>9 , поэтому мы продолжим, 2<9, поэтому мы нашли элемент, который меньше 9, который равен 2, так что теперь B[5]=3, потому что 3-это индекс 2.. я надеюсь, что это прояснило вопрос!

1 Ответов

Рейтинг:
7

Patrice T

Цитата:
я могу сделать это только O(n^2)

Ваш код не так уж плох, если массив отсортирован по возрастанию (1,2,3,4,5,6,7,8,9), то ваш код уже O(n), если массив отсортирован по убыванию (9,8,7,6,5,4,3,2,1), то ваш код O(n^2).
Небольшое улучшение в вашем коде:
B[0]=-1;
for(i=1;i<n;i++){
  B[i]=-1;
  for(j=(i-1);j>=0;j--){
    if(A[j] < A[i]){
      B[i]=j;
      break;
    }
    if(j=0){
      B[i]=-1;
    }
  }
}

Цитата:
я не могу придумать, как это сделать с O(n)

Я думаю, что точное O(n) невозможно достичь, но близко к этому возможно.
Примените свой код к (9,8,7,6,5,4,3,2,1) и (1,2,3,4,5,9,8,7,6), напишите списки и соответствующий им массив B. Попробуйте найти, как вы можете получить ответ на последний элемент с меньшей работой, чем проверка всех предыдущих элементов. Попробуйте найти короткие пути.

Конечно, я могу дать вам полное взрывное решение, но это разрушит цель вашего домашнего задания, и вы ничего не узнаете.

Чтобы измерить эффективность вашего кода, добавьте счетчик, чтобы узнать, сколько раз вы сравниваете 2 элемента списка.

[Обновление]
Чтобы узнать, является ли ваш код O(n) или чем-то еще, измените свой код следующим образом:
Cnti=0;
Cntj=0;
B[0]=-1;
for(i=1;i<n;i++){ 
  Cnti++;
  for(j=(i-1);j>=0;j--){
    Cntj++;
    if(A[j] < A[i]){
      B[i]=j;
      break;
    }
    if(j=0){
     B[i]=-1;
    }
  }
}
// code you have to write
// print n,Cnti,Cntj

и проанализируйте, как счетчики эволюционируют с размером Один
с помощью O(n) вы получите что-то вроде
3 3 9
5 5 15
10 10 30
с O(n^2) вы получите что-то вроде
3 3 9
5 5 25
10 10 100

Member 13791698

это не невозможно сделать ! мой профессор сделал это в O(n), а затем спросил, как это сделать, как будет, что означает, что это возможно, он дал нам подсказку использовать стек, но это совсем не помогло :/

Patrice T

Намек на стек без намека на то, что с ним делать, в основном бесполезен.
Сделайте то, что я вам сказал, и вы сможете улучшить свой код.

Member 13791698

Итак, если вы решили сделать это на c++, то я могу использовать стек, верно ? Итак , если я перебираю массив и каждый элемент помещаю его в стек , то я проверяю элемент сверху, он меньше, чем A[i], затем я помещаю его индекс в B[i], иначе я использую pop и проверяю следующий элемент .. теперь мой вопрос : doea pop n-1 раз потребляет O(n) ?

Patrice T

"doea pop n-1 раз потребляет O(n) ?"
Зависит от того, как вы это делаете в своем коде.
Обновление решения.

Member 13791698

хорошо, большое вам спасибо !!