Удаление элементов из массива величиной N за время O(n) и памятью O(1)

[Astrologer]

Собственно сабж. Есть какие нибудь мысли?

http://www.careercup.com/question?id=4794712
Оригинал.

[Igors]

Давеча обсуждали http://www.prog.org.ru/topic_14850_0.html
Вообще, вопрос удивляет 

[Astrologer]

Опять STL) Но топик просто удаление элемента с заданным условием. И честно говоря хотелось бы "пощупать" алгоритм, а не пользоваться STL.

Я например не могу понять как это сделать не сортируя массив? Сортировка за O(n) не бывает?

[Sancho_s_rancho]

Опять STL) Но топик просто удаление элемента с заданным условием. И честно говоря хотелось бы "пощупать" алгоритм, а не пользоваться STL.

Вам запретили смотреть код реализации STL?

[Astrologer]

А вы напишите код без STL,  я вам буду благодарен.

[Igors]

А вы напишите код без STL,  я вам буду благодарен.

Та я ж и написал в той же теме (пост #8) 

[Astrologer]

Извиняюсь, уточню задачу. Мы знаем что элементы в массиве варьируются от 1 до N.

[Astrologer]

Алгоритм с той же страницы вопроса.

Код

C++ (Qt)
vector<int> a;
  a.push_back(1);
  a.push_back(5);
  a.push_back(3);
  a.push_back(8);
  a.push_back(4);
  a.push_back(3);
  a.push_back(8);
  a.push_back(5);
  a.push_back(2);
  int n = a.size();
  for (int i=0;i<n;++i){
                  if(a[i]==i+1 || a[i]>n)
                          continue; 			//i.e. either inplace or duplicate
                  else{
                          while(true){
                                  if(a[i]>n) 		//i.e. a duplicate that is already detected
                                          break;
                                  if (a[a[i]-1]==a[i])
                                  {
                                          a[i]+=n;	//i.e. a duplicate is detected
                                          break;
                                  }
                                  swap(&a[i],&a[a[i]-1]);
                          }
                  }
          }
  vector<int> out;
  for (int i=0;i<n;++i){
                  if(a[i]<n)
                          out.push_back(a[i]);
          }
 

Время  О(3n)
Память О(1)

[Astrologer]

Вот мне интересно зачем такие вопросы задавать. Чтобы 90% кандидатов не прошли изначально? Или может быть кто то за 5 минут может прийти к подобному решению?

[spectre71]

Вот простой алгоритм:
сложность O(N);
доп память O(1);

Код

C
int removeDuplicateAndSort_ON_O1 (int* arr, int count) {
  int n, i;
 
  for(i=0; i<count; ++i) {                // check error values
    if(arr[i] < 1)     {return -1;}
    if(arr[i] > count) {return -1;}
  }  
 
  for(i=0; i<count;) {
    n = arr[i]-1;
    if(n == -1)         {++i; continue;}  // "Removed Value"
    if(n ==  i)         {++i; continue;}  // true place
    if(n ==  arr[n]-1)  {
      arr[i] = 0;                         // mark as "Removed Value"
      ++i; 
    } else {
      arr[i] = arr[n];                    // swap
      arr[n] = n+1;
    }
  }
 
  n = 0;           
  for(i=0; i<count; ++i) {                // remove "Removed Value"
    if(!arr[i]) {continue;}
    arr[n] = arr[i];
    ++n;
  }   
  return n;
}

[Igors]

Ага, оказывается надо удалять повторяющиеся элементы. А еще не указано можно ли менять порядок следованию (если можно то получается намного проще).  Ладно, полагаем нельзя. Тогда я бы делал так

Код

C++ (Qt)
void MarkDupAsNeg( int * arr, int n )
{
 for (int i = 0; i < n - 1; ++i) {
  int match = arr[i];
 
  if (match < 0)    
   continue;
 
  for (int j = i + 1; j < n; ++j) 
   if (arr[j] == match) 
    arr[i] = arr[j] = -1;
 } 
}
 
int RemoveNeg( int * arr, int n )
{
 int i, place = 0;
 for (i = 0; i < n; ++i) {
  if (arr[i] < 0) continue;
  if (i != place)
   arr[place] = arr[i];
  ++place;
 }
 return place;
}

Spectre, вероятно у Вас (как всегда) оптимальнее. Но оно же сложнее, шансы ошибиться резко возрастают 
Вообще такое ограничение на память делает задачу "академической" - в жизни почти все требует доп. памяти, другое дело этот расход должен быть разумным.

[spectre71]

Ага, оказывается надо удалять повторяющиеся элементы. А еще не указано можно ли менять порядок следованию (если можно то получается намного проще).  Ладно, полагаем нельзя. Тогда я бы делал так

Код

C++ (Qt)
 ... 

Spectre, вероятно у Вас (как всегда) оптимальнее. Но оно же сложнее, шансы ошибиться резко возрастают 
Вообще такое ограничение на память делает задачу "академической" - в жизни почти все требует доп. памяти, другое дело этот расход должен быть разумным.

Мой алгоритм не оптимальный(вернее не оптимизированный), я специально писал так, чтоб каждый шаг был понятен.

Задача ставилась сложность/время O(N) и память O(1) и запрет на изменение порядка элементов ограничения не накладывалось.
А в приведенном вами алгоритме сложность O(N^2) - всегда, и это оценка для лучшего случая.
Если у вас N == 100 или 1000, то возможно приемлимо использовать алгоритм O(N^2). Но если N == 1000000 (что не так много), то вы не дождетесь пока O(N^2) досчитает

- Если бы запрещалось менять порядок элементов, то задача решается  сложность O(N) и память O(N)
- Если значение элемента любое, но ограничено типом (например int), то задача тоже решается  сложность O(N) и память O(N), но для массивов малого размера оптимально применять сложность O(N^2) и память O(1) - например ваш.

[Igors]

Давайте прильнем к первоисточнику

Write a program to remove duplicate elements from array.(Array contains elements in range 1...N). Algorithm must be O(N) in time and O(1) in space. Come up with as many test cases as you can.

Подходит ли массив [5, 1, 5, 10] (4 элемента, диапазон 1..10) под условие задачи? Да, подходит. Sprectre, у Вас все прекрасно (линейная скорость) но только если "число элементов не меньше максимального значения" - не вижу такого условия.

Понятно что квадратичный перебор (строго говоря N ^ 2 / 2) никогда не хорош, но что делать практически? Ходов 2 - выделить память под указатели или прикинуть размер и смириться с тупым перебором (который имеет громадное достоинство что писать его несколько минут). А умирать в сложной/запутанной логике непрактично и ненужно.

[spectre71]

Давайте прильнем к первоисточнику

Write a program to remove duplicate elements from array.(Array contains elements in range 1...N). Algorithm must be O(N) in time and O(1) in space. Come up with as many test cases as you can.

Подходит ли массив [5, 1, 5, 10] (4 элемента, диапазон 1..10) под условие задачи? Да, подходит. Sprectre, у Вас все прекрасно (линейная скорость) но только если "число элементов не меньше максимального значения" - не вижу такого условия.

Понятно что квадратичный перебор (строго говоря N ^ 2 / 2) никогда не хорош, но что делать практически? Ходов 2 - выделить память под указатели или прикинуть размер и смириться с тупым перебором (который имеет громадное достоинство что писать его несколько минут). А умирать в сложной/запутанной логике непрактично и ненужно.

Я вообще-то думал что размер массива N. Иначе условие задачи не корректно.
- если Size > N, то алгоритм имеет сложность O(Size)!  Никогда  O(N)!
- если Size <= N , то алгоритм имеет сложность O(Size)! Можно сказать в условии O(N)!

Поскольку про Size ничего в условии не сказано, а при Size > N алгоритм со сложеностью O(N) невозможно построить, и считая условие задачи корректным выводим что Size == N

[spectre71]

А вот, новое условие.

Создать программу для удаления повторяющихся элементов из массива, изменение  порядка элементов допускается.
Размер массива N. Элементы массива - целые числа типа int.
Алгоритм должен быть:
- сложностью O(N)
- доп. память O(1)!

P.S. Для тех кто не в курсе: доп. память O(1) не означает 1 ячейка памяти, O(1) - означает, что кол-во  доп. памяти не зависит от N - т.е является константой. Но константа не INT_MAX

Это возможно!

Если никто не справится, то опишу алгоритм