Массив размером n, с одним элементом n / 2 раза

Question

Задан массив из n целых чисел, где один элемент встречается более чем в n / 2 раза Нам нужно найти этот элемент в линейном времени и постоянном дополнительном пространстве.

YAAQ: Еще один вопрос о массивах.

Answer 1

У меня есть подозрение, что это что-то вроде (в C #)

// We don't need an array
public int FindMostFrequentElement(IEnumerable<int> sequence)
{
    // Initial value is irrelevant if sequence is non-empty,
    // but keeps compiler happy.
    int best = 0; 
    int count = 0;

    foreach (int element in sequence)
    {
        if (count == 0)
        {
            best = element;
            count = 1;
        }
        else
        {
            // Vote current choice up or down
            count += (best == element) ? 1 : -1;
        }
    }
    return best;
}

Это звучит маловероятно, но это работает. ( Подтверждение в виде постскриптумного файла , любезно предоставлено Бойером / Муром.)

Answer 2

Найдите медиану, она занимает O (n) в несортированном массиве. Поскольку более n / 2 элементов равны одному значению, медиана также равна этому значению.

Answer 3

int findLeader(int n, int* x){
    int leader = x[0], c = 1, i;
    for(i=1; i<n; i++){
        if(c == 0){
            leader = x[i];
            c = 1;
        } else {
            if(x[i] == leader) c++;
            else c--;
        }
    }

    if(c == 0) return NULL;
    else {
        c = 0;
        for(i=0; i<n; i++){
            if(x[i] == leader) c++;
        }
        if(c > n/2) return leader;
        else return NULL;
    }
}

Я не автор этого кода, но это будет работать для вашей проблемы. Первая часть ищет потенциального лидера, вторая проверяет, появляется ли он в массиве более n / 2 раз.

Answer 4

Это то, что я думал изначально.

Я предпринял попытку сохранить инвариант «один элемент появляется более чем в n / 2 раза», уменьшая при этом набор проблем.

Давайте начнем сравнивать [i], a [i + 1]. Если они равны, мы сравниваем [i + i], a [i + 2]. Если нет, мы удаляем оба a [i], a [i + 1] из массива. Мы повторяем это, пока я> = (текущий размер) / 2. На этом этапе у нас будет элемент «THE», занимающий первые (текущий размер) / 2 позиции. Это будет поддерживать инвариант.

Единственное предостережение в том, что мы предполагаем, что массив находится в связанном списке [для его сложности O (n).]

Что говорят люди?

-bhupi

Answer 5

Ну, вы можете выполнить сортировку по осям радиуса, как описано здесь [pdf] , это не требует дополнительного пространства и линейного времени. затем вы можете сделать один проход, считая последовательные элементы и заканчивая счетом> n / 2.

Answer 6

int n = A.Length;
            int[] L = new int[n + 1];
            L[0] = -1;
            for (int i = 0; i < n; i++)
            {
                L[i + 1] = A[i];
            }
            int count = 0;
            int pos = (n + 1) / 2;
            int candidate = L[pos];
            for (int i = 1; i <= n; i++)
            {
                if (L[i] == candidate && L[pos++] == candidate)
                    return candidate;
            }
            if (count > pos)
                return candidate;
            return (-1);

Answer 7

в php --- пожалуйста, проверьте правильность

function arrLeader( $A ){
$len = count($A);
$B = array();
$val=-1;
$counts = array_count_values(array); //return array with elements as keys and occurrences of each element as values
for($i=0;$i<$len;$i++){
    $val = $A[$i];
    if(in_array($val,$B,true)){//to avoid looping again and again
    }else{
     if($counts[$val]>$len/2){
      return $val;
     }
     array_push($B, $val);//to avoid looping again and again
    }
 }
 return -1;
}

Answer 8

Как насчет: случайным образом выберите небольшое подмножество из K элементов и найдите дубликаты (например, первые 4, первые 8 и т. д.). Если K == 4, то вероятность не получить как минимум 2 дубликата составляет 1/8. если K == 8, то оно становится менее 1%. Если вы не нашли дубликатов, повторите процедуру, пока не сделаете. (Предполагая, что другие элементы распределены более случайным образом, это будет работать очень плохо, скажем, с 49% массива = "A", 51% массива = "B").

например:

findDuplicateCandidate: 
    select a fixed size subset.
    return the most common element in that subset
    if there is no element with more than 1 occurrence repeat.
    if there is more than 1 element with more than 1 occurrence call findDuplicate and choose the element the 2 calls have in common    

Это операция постоянного порядка (если набор данных не плохой), поэтому выполните линейное сканирование массива, чтобы (N) проверить.

Answer 9

Моей первой мыслью (недостаточно) было бы:

• Сортировать массив по месту
• Вернуть средний элемент

Но это будет O (n log n), как и любое рекурсивное решение.

Если вы можете деструктивно модифицировать массив (и применяются различные другие условия), вы можете выполнить проход, заменив элементы их количеством или чем-то еще. Знаете ли вы что-нибудь еще о массиве и можете ли вы его изменять?

Редактировать Оставив здесь свой ответ для потомков, но я думаю, что Скит получил его.