Число, которое больше чем n/3 раза в массиве

Ответ 1

Ответ Джона Дворака, вероятно, лучше всего:

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

В конце сделайте второй проход по массиву, чтобы проверить, действительно ли у кандидатов есть требуемый счетчик. Это не разрешено вопросом, на который вы ссылаетесь, но я не вижу, как избежать его для этой модифицированной версии. Если есть значение, которое больше, чем n/3 раза, то оно будет в слоте, но вы не знаете, какой из них он имеет.

Если эта модифицированная версия вопроса гарантировала наличие двух значений с более чем n/3 элементами (в общем случае k-1 с более чем n/k), нам не понадобится второй проход. Но когда исходный вопрос имеет k=2 и 1 гарантированное большинство, нет способа узнать, следует ли "обобщать" его как гарантию 1 такого элемента или гарантировать k-1. Чем сильнее гарантия, тем легче проблема.

Ответ 2

Используя алгоритм голосования Бойера-Мура большинства, получим:

vector<int> majorityElement(vector<int>& nums) {
    int cnt1=0, cnt2=0;
    int a,b;
    for(int n: nums){
        if (cnt1 == 0 || n == a){
            cnt1++;
            a = n;
        }
        else if (cnt2 == 0 || n==b){
            cnt2++;
            b = n;
        }
        else{
            cnt1--;
            cnt2--;
        }
    }
    cnt1=cnt2=0;
    for(int n: nums){
        if (n==a) cnt1++;
        else if (n==b) cnt2++;
    }
    vector<int> result;
    if (cnt1 > nums.size()/3) result.push_back(a);
    if (cnt2 > nums.size()/3) result.push_back(b);
    return result;
}

Ответ 3

Вы можете использовать алгоритм выбора, чтобы найти номер в n/3 месте и 2n/3.

n1=Selection(array[],n/3);
n2=Selection(array[],n2/3);
coun1=0;
coun2=0;

for(i=0;i<n;i++)
{
    if(array[i]==n1)
      count1++;
    if(array[i]==n2)
      count2++;
}
if(count1>n)
   print(n1);
else if(count2>n)
   print(n2);
else
   print("no found!");

Ответ 4

В строке с номером пять оператор if должен иметь еще одну проверку:

if(n!=b && (cnt1 == 0 || n == a))

Ответ 5

Если в массиве есть n элементов, и предположим, что в худшем случае только 1 элемент повторяется n/3 раза, тогда вероятность выбора одного числа, а не того, которое повторяется n/3 раза, будет (2n/3 )/n, что равно 1/3, поэтому, если мы случайным образом выберем N элементов из массива размера 'n, то вероятность того, что мы в итоге выберем n/3 раза повторное число, будет по крайней мере 1- (2/3) ^ N Если мы вычислим это, чтобы сказать 99,99% вероятности успеха, мы получим N = 23 для любого значения "n".

Поэтому просто выберите 23 числа случайным образом из списка и посчитайте их вхождения, если мы получим число больше n/3, мы вернем это число, и если мы не получили никакого решения после случайной проверки 23 чисел, вернем -1;

Алгоритм по сути O (n), так как значение 23 не зависит от n (размер списка), поэтому мы должны просто 23 раза пересечь массив в худшем случае алгоритма.

Принятый код на собеседовании (C++):

  int n=A.size();
  int ans,flag=0;
  for(int i=0;i<23;i++)
  {

int index=rand()%n;
int elem=A[index];
int count=0;
for(int i=0;i<n;i++)
{
    if(A[i]==elem)
    count++;
}

if(count>n/3)
{
    flag=1;
    ans=elem;
}

if(flag==1)
break;
}

if(flag==1)
 return ans;
else return -1;
 }

Ответ 6

Я использую следующее решение Python для обсуждения правильности алгоритма:

class Solution:
    """
    @param: nums: a list of integers
    @return: The majority number that occurs more than 1/3
    """
    def majorityNumber(self, nums):
        if nums is None:
            return None
        if len(nums) == 0:
            return None

        num1 = None
        num2 = None
        count1 = 0
        count2 = 0

        # Loop 1
        for i, val in enumerate(nums):
            if count1 == 0:
                num1 = val
                count1 = 1
            elif val == num1:
                count1 += 1
            elif count2 == 0:
                num2 = val
                count2 = 1
            elif val == num2:
                count2 += 1
            else:
                count1 -= 1
                count2 -= 1


        count1 = 0
        count2 = 0

        for val in nums:
            if val == num1:
                count1 += 1
            elif val == num2:
                count2 += 1

        if count1 > count2:
            return num1

        return num2

Сначала нам нужно доказать утверждение А:

Утверждение A: рассмотрим список C который содержит мажоритарное число m которое встречается больше floor(n/3) раз. После того, как 3 разных числа удалены из C, мы имеем C'. m является мажоритарным числом C'.

Доказательство: используйте R чтобы обозначить число вхождений m в C У нас R > floor(n/3). R > floor(n/3) => R - 1 > floor(n/3) - 1 => R - 1 > floor((n-3)/3). Используйте R' чтобы обозначить число вхождений m в C'. И используйте n' чтобы обозначить длину C'. Так как 3 разных числа удалены, мы имеем R' >= R - 1. И n'=n-3 очевидно. Мы можем иметь R' > floor(n'/3) из R - 1 > floor((n-3)/3). Таким образом, m является мажоритарным числом C'.

Теперь докажем правильность loop 1. Определите L как count1 * [num1] + count2 * [num2] + nums[i:]. Используйте m для обозначения номера большинства.

инвариантный

Большая часть m находится в L

инициализация

В начале первой итерации L - это числа nums[0:]. Таким образом, инвариант тривиально верен.

техническое обслуживание

1. if count1 == 0: перед итерацией L будет count2 * [num2] + nums[i:]. После итерации L равно 1 * [nums[i]] + count2 * [num2] + nums[i+1:]. Другими словами, L не изменяется. Таким образом, инвариант сохраняется.

2. if val == num1 ветвь if val == num1: перед итерацией L равно count1 * [nums[i]] + count2 * [num2] + nums[i:]. После итерации L равно (count1+1) * [num[i]] + count2 * [num2] + nums[i+1:]. Другими словами, L не изменяется. Таким образом, инвариант сохраняется.

3. f count2 == 0 ответвление: аналогично условию 1.
4. elif val == num2 ветвь elif val == num2: аналогично условию 2.
5. else отрасль: nums[i], num1 и num2 отличаются друг от друга в этом случае. После итерации L равно (count1-1) * [num1] + (count2-1) * [num2] + nums[i+1:]. Другими словами, три разных числа перемещаются из count1 * [num1] + count2 * [num2] + nums[i:]. Из утверждения A мы знаем, что m является мажоритарным числом L что инвариант сохраняется.

прекращение

Когда цикл заканчивается, nums[n:] пуст. L равно count1 * [num1] + count2 * [num2].

Поэтому, когда цикл завершается, число большинства либо num1 или num2.