Сортировка вопросов, как получить доступ к частным векторным значениям

Question

Я делаю эту проблему при сортировке, которая, как мне кажется, может быть отсортирована с помощью сортировки по кучи или быстрой сортировки.

Существует массив A целых чисел размера n, к которому нет прямого доступа. Однако вы можете получить истинный или ложный ответ на запросы в форме A [i]

class hiddenVector {
        private:
             vector <int> data; // you cannot directly access this in your code since this is a private element
        public:
             int getSize();// it returns a non-negative integer equal to the size of the class member data.
             bool iLessThanj(int i, int j); // returns true if and only if data[i] is strictly less than data[j]

};

Answer 1

Вы можете создать новый вектор, который содержит индексы скрытого вектора, а затем отсортировать его, используя открытый метод iLessThanj() скрытого вектора.Наконец, просмотрите отсортированные индексы, чтобы найти пару одинаковых элементов, они являются смежными после сортировки и iLessThanj(i, i+1) == false для них и только для них.

Это имеет сложность O (nlogn) во времени и O (n) в памяти.

hiddenVector a; // {1, 3, -2, -4, 3, 7} for example
// construct indexes array
std::vector<int> a_ind (a.getSize ());
for (int i = 0; i < a.getSize(); i++)
  a_ind[i] = i;

// now a_ind = {0, 1, 2, 3, 4, 5}
// sort it
std::sort(begin(a_ind), end(a_ind),
      [&a] (int i, int j) { return a.iLessThanj(i, j); }
);
// now a_ind = {3, 2, 0, 1, 4, 5} 
// and it is equal to sequence of indexes in sorted hidden vector

// finally, compute an answer to your problem
std::pair<int, int> res = {};
for (int k = 0; k < a_ind.size()-1; k++) {
  int i = a_ind[k];
  int j = a_ind[k+1];
  if (!a.iLessThanj(i, j)) {
    res.first = i;
    res.second = j;
    break;
  }
}
// now res = {1, 4}

PS Результаты Speedtest для обсуждения в комментариях (скомпилировано и запущено с -O3):

N      squared_algo sublinear_algo
10     2.259e-07    1.1653e-06 
100    4.8259e-06   8.5859e-06 
1000   0.000218602  0.000118063 
10000  0.0138744    0.000718756 
100000 0.913739     0.00876182

Полный код быстрого теста здесь

Answer 2

Дано, что у A есть только одна дублирующаяся пара, а все остальные элементы различны.Таким образом, он имеет n-1 различных элементов и 1 элемент, который совпадает с одним из n-1 элементов.Ваша задача - определить индексы двух идентичных элементов в A.

, вам не нужно обращаться к элементам, индексам a и b являются решением, когда iLessThanj(a, b) возвращает false и iLessThanj(b, a) также возвращает false (конечно, с b ! = a )

, поэтому что-то вроде:

hiddenVector v;
... initialization of v
int n = v.getSize();

for (int a = 0; a < n; ++a) {
  int b;

  for (b = a+1; b < n; ++b) {
     if (!v.iLessThanj(a, b) && !v.iLessThanj(b, a)) {
       std::cout << "element is the same at indexes " << a << " and " << b << std::endl;
       break;
     }
  }
  if (b < n)
    break;
}

PS сложность O (n ^ 2), посмотрите на другой ответ, более сложный, но с меньшей сложностью