Использование массива и перемещение дубликатов до конца

Question

Я получил этот вопрос на собеседовании, и в конце мне сказали, что есть более эффективный способ сделать это, но до сих пор не удалось его выяснить. Вы передаете в функцию массив целых чисел и целое число для размера массива. В массиве у вас много чисел, некоторые из которых повторяются, например, 1,7,4,8,2,6,8,3,7,9,10. Вы хотите взять этот массив и вернуть массив, в котором все повторяющиеся числа помещены в конец массива, чтобы приведенный выше массив превратился в 1,7,4,8,2,6,3,9,10,8,7. Числа, которые я использовал, не важны, и я не мог использовать буферный массив. Я собирался использовать BST, но порядок номеров должен быть сохранен (за исключением дублирующих номеров). Я не мог понять, как использовать хеш-таблицу, поэтому я использовал двойной цикл for (n ^ 2 ужасно, я знаю). Как бы я сделал это более эффективно с помощью C ++. Не ищу код, просто идея, как это сделать лучше.

Answer 1

Далее:

1. arr - входной массив;
2. seen - это уже найденный хэш-набор чисел;
3. l - это индекс, в который будет помещен следующий уникальный элемент;
4. r - это индекс следующего рассматриваемого элемента.

Поскольку вы не ищете кодВот псевдокодовое решение (которое является допустимым Python):

arr = [1,7,4,8,2,6,8,3,7,9,10]
seen = set()
l = 0
r = 0
while True:
  # advance `r` to the next not-yet-seen number
  while r < len(arr) and arr[r] in seen:
    r += 1
  if r == len(arr): break
  # add the number to the set
  seen.add(arr[r])
  # swap arr[l] with arr[r]
  arr[l], arr[r] = arr[r], arr[l]
  # advance `l`
  l += 1
print arr

В вашем тестовом примере это выдает

[1, 7, 4, 8, 2, 6, 3, 9, 10, 8, 7]

Answer 2

Я был не в курсе какое-то время, но я, вероятно, начну с чего-то подобного и посмотрю, как оно масштабируется с большим вводом.Я знаю, что вы не просили код, но в некоторых случаях это легче понять, чем объяснить.

Редактировать: Извините, я пропустил требование, что вы не можете использовать буферный массив.

// returns new vector with dupes a the end
std::vector<int> move_dupes_to_end(std::vector<int> input)
{
    std::set<int> counter;
    std::vector<int> result;
    std::vector<int> repeats;

    for (std::vector<int>::iterator i = input.begin(); i < input.end(); i++)
    {
        if (counter.find(*i) == counter.end())
            result.push_back(*i);
        else
            repeats.push_back(*i);
        counter.insert(*i);
    }

    result.insert(result.end(), repeats.begin(), repeats.end());

    return result;
}

Answer 3

#include <algorithm>

T * array = [your array];
size_t size = [array size];
                                           // Complexity:
sort( array, array + size );               // n * log(n) and could be threaded
                                           // (if merge sort)
T * last = unique( array, array + size );  // n, but the elements after the last
                                           // unique element are not defined

Чек sort и unique.

Answer 4

Если вы знаете границы целых значений B и размер массива целых чисел SZ, то вы можете сделать что-то вроде следующего:

1. Создать массив логических значений seen_before с B элементами, инициализированными в 0.
2. Создать результирующий массив result целых чисел с SZ элементами.
3. Создайте два целых числа, одно для front_pos = 0, другое для back_pos = SZ - 1.
4. Итерация по исходному списку:
   • Установить целочисленную переменную val равной значению текущего элемента
   • Если seen_before[val] установлено в 1, введите число в result[back_pos], затем уменьшите back_pos
   • Если seen_before[val] не установлено в 1, введите число в result[front_pos], затем увеличьте front_pos и установите seen_before[val] в 1.

Как только вы закончите итерацию по основному списку, все уникальные номера будут в начале списка, в то время как повторяющиеся номера будут в конце. Самое интересное, что весь процесс выполняется за один проход. Обратите внимание, что это работает, только если вы знаете границы значений, появляющихся в исходном массиве.

Редактировать: Было отмечено, что нет границ для используемых целых чисел, поэтому вместо инициализации seen_before как массива с элементами B, инициализируйте его как map<int, bool>, затем продолжите по-прежнему. Это должно дать вам n * log (n) производительность.

Answer 5

void remove_dup(int* data, int count) {
    int* L=data; //place to put next unique number
    int* R=data+count; //place to place next repeat number
    std::unordered_set<int> found(count); //keep track of what's been seen
    for(int* cur=data; cur<R; ++cur) { //until we reach repeats
        if(found.insert(*cur).second == false) { //if we've seen it
            std::swap(*cur,*--R); //put at the beginning of the repeats
        } else                    //or else
            std::swap(*cur,*L++); //put it next in the unique list
    }
    std::reverse(R, data+count); //reverse the repeats to be in origional order
}

http://ideone.com/3choA
Не то чтобы я включил в код это плохо прокомментировал. Также обратите внимание, что unordered_set, вероятно, использует свой собственный массив внутри, больше чем data. (Это было переписано на основе ответа AIX, чтобы быть намного быстрее)

Answer 6

Я бы использовал дополнительную карту, где ключом является целочисленное значение из массива, а значением является целое число, установленное в 0 в начале.Теперь я бы прошел массив и увеличил значения на карте, если ключ уже есть на карте.В конце я бы снова прошел через массив.Когда целое число из массива имеет значение единицы на карте, я ничего не буду менять.Если значение на карте равно 2 или более, я заменяю целое число из массива на последний.

Это должно привести к времени выполнения O (n * log (n))

Answer 7

Я бы сделал так, чтобы создать массив в два раза больше исходного и создать набор целых чисел.

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

В конце вы получите массив, который выглядит следующим образом: (на вашем примере)

1,7,4,8,2,6,3,9,10, -, -, 8,7, -, -, -, -, -, -, -, -, -

Затем я бы снова перебрал исходный массив и сделал каждую точку равной следующей ненулевой позиции (или 0, или как вы решили)

Это бы заставило исходный массив превратиться в ваше решение...

В итоге получается, что O (n) настолько эффективен, насколько я могу представить,

Edit: since you can not use another array, when you find a value that is already in the
set you can move every value after it forward one and set the last value equal to the
number you just checked, this would in effect do the same thing but with a lot more operations.

Answer 8

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

Реализация Java:

public static void solve() {
                Integer[] arr = new Integer[] { 1, 7, 4, 8, 2, 6, 8, 3, 7, 9, 10 };
        final HashSet<Integer> seen = new HashSet<Integer>();
        int l = -1;

        for (int i = 0; i < arr.length; i++) {
            if (seen.contains(arr[i])) {
                if (l == -1) {
                    l = i;
                }
                continue;
            }
            if (l > -1) {
                final int temp = arr[i];
                arr[i] = arr[l];
                arr[l] = temp;
                l++;
            }
            seen.add(arr[i]);
        }

    }

вывод 1 7 4 8 2 6 3 9 10 8 7

Answer 9

void move_duplicates_to_end(vector<int> &A) {
    if(A.empty()) return;
    int i = 0, tail = A.size()-1;
    while(i <= tail) {
        bool is_first = true;    // check of current number is first-shown
        for(int k=0; k<i; k++) { // always compare with numbers before A[i]
            if(A[k] == A[i]) {
                is_first = false;
                break;
            }
        }
        if(is_first == true) i++;
        else {
            int tmp = A[i]; // swap with tail
            A[i] = A[tail];
            A[tail] = tmp;
            tail--;
        }
    }

Если входной массив {1,7,4,8,2,6,8,3,7,9,10}, то выходной сигнал равен {1,7,4,8,2,6,10 , 3,9,7,8}. По сравнению с вашим ответом {1,7,4,8,2,6,3,9,10,8,7}, первая половина та же, а правая половина отличается, потому что я поменяю местами все дубликаты массива. Как вы упомянули, порядок дубликатов может быть произвольным.

Answer 10

Это некрасиво, но отвечает требованиям перемещения дубликатов до конца на месте (без буферного массива)

// warning, some light C++11
void dup2end(int* arr, size_t cnt)
{
   std::set<int> k;
   auto end = arr + cnt-1;
   auto max = arr + cnt;
   auto curr = arr;

   while(curr < max)
   {
      auto res = k.insert(*curr);

      // first time encountered
      if(res.second)
      {
         ++curr;
      }
      else
      {
         // duplicate:
         std::swap(*curr, *end);
         --end;
         --max;
      }
   }
}