Как найти первый неповторяющийся элемент? - PullRequest
5 голосов
/ 15 августа 2011

Как найти первый неповторяющийся элемент в массиве. При условии, что вы можете использовать только 1 бит для каждого элемента массива, а временная сложность должна быть O (n), где n - длина массива. Пожалуйста, убедитесь, что я как-то наложил ограничения на требования к памяти. Также возможно, что это не может быть сделано только с дополнительным битом на элемент строки. Также, пожалуйста, дайте мне знать, если это возможно или нет?

Ответы [ 4 ]

3 голосов
/ 15 августа 2011

Я бы сказал, что нет алгоритма, основанного на сравнении, который может сделать это за O (n). Поскольку вы должны сравнить первый элемент массива со всеми остальными, второй - со всеми, кроме первого, третий - со всеми, кроме первого = Sum i = O (n ^ 2).

(Но это не обязательно означает, что не существует более быстрого алгоритма, см. Сортировку: есть доказательство того, что вы не можете сортировать быстрее, чем O (n log n), если вы основаны на сравнении - и действительно есть один более быстрый: Bucket Сортировка, которая может сделать это в O (n)).

РЕДАКТИРОВАТЬ : В одном из других комментариев я сказал кое-что о хэш-функциях. Я проверил некоторые факты об этом, и вот мысли о подходе hashmap:

  • Очевидный подход (в псевдокоде):

    for (i = 0; i < maxsize; i++)
        count[i] = 0;
    for (i = 0; i < maxsize; i++) {
       h = hash(A[i]);
       count[h]++;
    }
    first = -1;
    for (i = 0; i < maxsize; i++)
       if (count[i] == 0) {
          first = i;
          break;
       }
    }
    for (i = 0; hash(A[i]) != first; i++) ;
    printf("first unique: " + A[i]); 
    
  • Есть несколько предостережений:

    1. Как получить hash. Я провел некоторое исследование по идеальным хэш-функциям. И действительно, вы можете сгенерировать один в O (n). ( Оптимальные алгоритмы для минимального идеального хеширования Джорджа Хаваса и др. - Не уверен, насколько хорош этот документ, поскольку он утверждает, что Time Limit O (n), но говорит о нелинейном ограничении пространства (который является планом ошибка, я надеюсь, что я не единственный, видящий недостаток в этом, но согласно всем теоретическим компьютерным наукам, которые я знаю, время - верхняя граница для пространства (поскольку у вас нет времени писать в большем количестве пространства)). Но я верю их, когда они говорят, что это возможно в O (N).

    2. Дополнительное пространство - здесь я не вижу решения. Выше статьи цитируют некоторые исследования, в которых говорится, что вам нужно 2,7 бит для идеальной хэш-функции. С дополнительным массивом count (который можно сократить до состояний: Пустой + 1 Элемент + Больше чем 1 Элемент) вам нужно 2 дополнительных бита на элемент (1,58, если вы предполагаете, что это может каким-то образом сочетаться с вышеприведенным 2.7), что суммирует до 5 дополнительных битов.

1 голос
/ 16 августа 2011

Здесь я просто предполагаю, что это строка Character String, содержащая только маленькие алфавиты, так что я могу использовать одно целое число (32 бита), чтобы при 26 алфавитах было достаточно взять один бит на алфавит.Раньше я думал взять массив из 256 элементов, но тогда он будет иметь 256 * 32 бита.32 бита на элемент.Но в конце концов я обнаружил, что не смогу сделать это без еще одной переменной.Таким образом, решение похоже на это с одним целым числом (32 бита) для 26 алфавитов:

 int print_non_repeating(char* str)
 {
  int bitmap = 0, bitmap_check = 0;
  int length = strlen(str);
  for(int i=0;i<len;i++)
  {
   if(bitmap & 1<<(str[i] - 'a'))
     {
        bitmap_check = bitmap_check | ( 1 << (str[i] - 'a');
      }
   else 
      bitmap = bitmap | (1 << str[i] - 'a');
  }
  bitmap = bitmap ^ bitmap_check;
  i = 0;
  if(bitmap != 0)
  {
  while(!bitmap & (1<< (str[i])))
   i++;
  cout<<*(str+i);
   return 1;
  }
  else 
  return 0;
  }
0 голосов
/ 15 августа 2011

Вы можете попробовать выполнить модифицированную сортировку сегментов, как показано ниже. Однако вам необходимо знать максимальное значение в массиве, передаваемое в метод firstNonRepeat. Так что это работает на O (N). Для методов, основанных на сравнении, теоретически самым быстрым (по крайней мере, с точки зрения сортировки) является O (n log n). В качестве альтернативы, вы можете даже использовать модифицированные версии сортировки radix для достижения этой цели.

public class BucketSort{
    //maxVal is the max value in the array
    public int firstNonRepeat(int[] a, int maxVal){
        int [] bucket=new int[maxVal+1];

        for (int i=0; i<bucket.length; i++){
            bucket[i]=0;
        }

        for (int i=0; i<a.length; i++){
            if(bucket[a[i]] == 0) {
                bucket[a[i]]++;             
            } else {
                return bucket[a[i]];
            }
        }
    }
}
0 голосов
/ 15 августа 2011

Этот код находит первый повторяющийся элемент.еще не разобрался, если в том же цикле for можно найти неповторяющийся элемент, не вводя другой for (чтобы сохранить код O (n)).Другие ответы предлагают пузырьковую сортировку, которая является O (n ^ 2)

#include <iostream>
using namespace std;
#define max_size 10

int main()
{
    int numbers[max_size] = { 1, 2, 3, 4, 5, 1, 3, 4 ,2, 7};
    int table[max_size] = {0,0,0,0,0,0,0,0,0,0};
    int answer = 0, j=0;

  for (int i = 0; i < max_size; i++)
  {
    j = numbers[i] %max_size;
    table[j]++;
    if(table[j] >1)
    {
          answer = 1;
          break;
    }
 }
   std::cout << "answer = " << answer ;
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...