Как найти самый частый элемент массива

Given an array, find the most frequent element in it. If there are multiple elements that appear a maximum number of times, print any one of them.

Examples:

Input : arr[] = {1, 3, 2, 1, 4, 1}
Output : 1
Explanation: 1 appears three times in array which is maximum frequency.

Input : arr[] = {10, 20, 10, 20, 30, 20, 20}
Output : 20

A simple solution is to run two loops. The outer loop picks all elements one by one. The inner loop finds the frequency of the picked element and compares it with the maximum so far.

Implementation:

C++

#include <bits/stdc++.h>

using namespace std;

int mostFrequent(int* arr, int n)

{

int maxcount = 0;

int element_having_max_freq;

for (int i = 0; i < n; i++) {

int count = 0;

for (int j = 0; j < n; j++) {

if (arr[i] == arr[j])

count++;

}

if (count > maxcount) {

maxcount = count;

element_having_max_freq = arr[i];

}

return element_having_max_freq;

}

int main()

{

int arr[] = { 40, 50, 30, 40, 50, 30, 30 };

int n = sizeof(arr) / sizeof(arr[0]);

cout << mostFrequent(arr, n);

return 0;

}

Java

public class GFG

{

public static int mostFrequent(int[] arr, int n)

{

int maxcount = 0;

int element_having_max_freq = 0;

for (int i = 0; i < n; i++) {

int count = 0;

for (int j = 0; j < n; j++) {

if (arr[i] == arr[j]) {

count++;

}

if (count > maxcount) {

maxcount = count;

element_having_max_freq = arr[i];

}

return element_having_max_freq;

}

public static void main(String[] args)

{

int[] arr = { 40, 50, 30, 40, 50, 30, 30 };

int n = arr.length;

System.out.print(mostFrequent(arr, n));

}

Python3

def mostFrequent(arr, n):

maxcount = 0;

element_having_max_freq = 0;

for i in range(0, n):

count = 0

for j in range(0, n):

if(arr[i] == arr[j]):

count += 1

if(count > maxcount):

maxcount = count

element_having_max_freq = arr[i]

return element_having_max_freq;

arr = [40,50,30,40,50,30,30]

n = len(arr)

print(mostFrequent(arr, n))

C#

using System;

public class GFG

{

public static int mostFrequent(int[] arr, int n)

{

int maxcount = 0;

int element_having_max_freq = 0;

for (int i = 0; i < n; i++) {

int count = 0;

for (int j = 0; j < n; j++) {

if (arr[i] == arr[j]) {

count++;

}

if (count > maxcount) {

maxcount = count;

element_having_max_freq = arr[i];

}

return element_having_max_freq;

}

public static void Main(String[] args)

{

int[] arr = { 40, 50, 30, 40, 50, 30, 30 };

int n = arr.Length;

Console.Write(mostFrequent(arr, n));

}

Javascript

function mostFrequent(arr, n) {

let maxcount = 0;

let element_having_max_freq;

for (let i = 0; i < n; i++) {

let count = 0;

for (let j = 0; j < n; j++) {

if (arr[i] == arr[j])

count++;

}

if (count > maxcount) {

maxcount = count;

element_having_max_freq = arr[i];

}

return element_having_max_freq;

}

let arr = [40, 50, 30, 40, 50, 30, 30];

let n = arr.length;

console.log(mostFrequent(arr, n));

The time complexity of this solution is O(n²) since 2 loops are running from i=0 to i=n we can improve its time complexity by taking a visited array and skipping numbers for which we already calculated the frequency.
Auxiliary space: O(1) as it is using constant space for variables

A better solution is to do the sorting. We first sort the array, then linearly traverse the array.

Implementation:

C++

#include <bits/stdc++.h>

using namespace std;

int mostFrequent(int arr[], int n)

{

sort(arr, arr + n);

int max_count = 1, res = arr[0], curr_count = 1;

for (int i = 1; i < n; i++) {

if (arr[i] == arr[i - 1])

curr_count++;

else

curr_count = 1;

if (curr_count > max_count) {

max_count = curr_count;

res = arr[i - 1];

}

return res;

}

int main()

{

int arr[] = { 40,50,30,40,50,30,30};

int n = sizeof(arr) / sizeof(arr[0]);

cout << mostFrequent(arr, n);

return 0;

}

C

#include <stdio.h>

#include <stdlib.h>

int cmpfunc(const void* a, const void* b)

{

return (*(int*)a - *(int*)b);

}

int mostFrequent(int arr[], int n)

{

qsort(arr, n, sizeof(int), cmpfunc);

int max_count = 1, res = arr[0], curr_count = 1;

for (int i = 1; i < n; i++) {

if (arr[i] == arr[i - 1])

curr_count++;

else

curr_count = 1;

if (curr_count > max_count) {

max_count = curr_count;

res = arr[i - 1];

}

return res;

}

int main()

{

int arr[] = { 40,50,30,40,50,30,30};

int n = sizeof(arr) / sizeof(arr[0]);

printf("%d", mostFrequent(arr, n));

return 0;

}

Java

import java.util.*;

class GFG {

static int mostFrequent(int arr[], int n)

{

Arrays.sort(arr);

int max_count = 1, res = arr[0];

int curr_count = 1;

for (int i = 1; i < n; i++) {

if (arr[i] == arr[i - 1])

curr_count++;

else

curr_count = 1;

if (curr_count > max_count) {

max_count = curr_count;

res = arr[i - 1];

}

return res;

}

public static void main(String[] args)

{

int arr[] = { 40,50,30,40,50,30,30};

int n = arr.length;

System.out.println(mostFrequent(arr, n));

}

Python3

def mostFrequent(arr, n):

arr.sort()

max_count = 1

res = arr[0]

curr_count = 1

for i in range(1, n):

if (arr[i] == arr[i - 1]):

curr_count += 1

else:

curr_count = 1

if (curr_count > max_count):

max_count = curr_count

res = arr[i - 1]

return res

arr = [40,50,30,40,50,30,30]

n = len(arr)

print(mostFrequent(arr, n))

C#

using System;

class GFG {

static int mostFrequent(int[] arr, int n)

{

Array.Sort(arr);

int max_count = 1, res = arr[0];

int curr_count = 1;

for (int i = 1; i < n; i++) {

if (arr[i] == arr[i - 1])

curr_count++;

else

curr_count = 1;

if (curr_count > max_count) {

max_count = curr_count;

res = arr[i - 1];

}

return res;

}

public static void Main()

{

int[] arr = {40,50,30,40,50,30,30 };

int n = arr.Length;

Console.WriteLine(mostFrequent(arr, n));

}

PHP

<?php

function mostFrequent( $arr, $n)

{

sort($arr);

sort($arr , $n);

$max_count = 1;

$res = $arr[0];

$curr_count = 1;

for ($i = 1; $i < $n; $i++)

{

if ($arr[$i] == $arr[$i - 1])

$curr_count++;

else

$curr_count = 1;

if ($curr_count > $max_count)

{

$max_count = $curr_count;

$res = $arr[$i - 1];

}

return $res;

}

{

$arr = array(40,50,30,40,50,30,30);

$n = sizeof($arr) / sizeof($arr[0]);

echo mostFrequent($arr, $n);

return 0;

}

?>

Javascript

<script>

function mostFrequent(arr, n)

{

arr.sort();

let max_count = 1, res = arr[0];

let curr_count = 1;

for (let i = 1; i < n; i++)

{

if (arr[i] == arr[i - 1])

curr_count++;

else

curr_count = 1;

if (curr_count > max_count)

{

max_count = curr_count;

res = arr[i - 1];

}

return res;

}

let arr = [40,50,30,40,50,30,30];

let n = arr.length;

document.write(mostFrequent(arr,n));

</script>

Time Complexity: O(nlog(n))
Auxiliary Space: O(1)

An efficient solution is to use hashing. We create a hash table and store elements and their frequency counts as key-value pairs. Finally, we traverse the hash table and print the key with the maximum value.

C++

#include <bits/stdc++.h>

using namespace std;

int mostFrequent(int arr[], int n)

{

unordered_map<int, int> hash;

for (int i = 0; i < n; i++)

hash[arr[i]]++;

int max_count = 0, res = -1;

for (auto i : hash) {

if (max_count < i.second) {

res = i.first;

max_count = i.second;

}

return res;

}

int main()

{

int arr[] = {40,50,30,40,50,30,30 };

int n = sizeof(arr) / sizeof(arr[0]);

cout << mostFrequent(arr, n);

return 0;

}

Java

import java.util.HashMap;

import java.util.Map;

import java.util.Map.Entry;

class GFG {

static int mostFrequent(int arr[], int n)

{

Map<Integer, Integer> hp =

new HashMap<Integer, Integer>();

for(int i = 0; i < n; i++)

{

int key = arr[i];

if(hp.containsKey(key))

{

int freq = hp.get(key);

freq++;

hp.put(key, freq);

}

else

{

hp.put(key, 1);

}

int max_count = 0, res = -1;

for(Entry<Integer, Integer> val : hp.entrySet())

{

if (max_count < val.getValue())

{

res = val.getKey();

max_count = val.getValue();

}

return res;

}

public static void main (String[] args) {

int arr[] = {40,50,30,40,50,30,30};

int n = arr.length;

System.out.println(mostFrequent(arr, n));

}

Python3

import math as mt

def mostFrequent(arr, n):

Hash = dict()

for i in range(n):

if arr[i] in Hash.keys():

Hash[arr[i]] += 1

else:

Hash[arr[i]] = 1

max_count = 0

res = -1

for i in Hash:

if (max_count < Hash[i]):

res = i

max_count = Hash[i]

return res

arr = [ 40,50,30,40,50,30,30]

n = len(arr)

print(mostFrequent(arr, n))

C#

using System;

using System.Collections.Generic;

class GFG

{

static int mostFrequent(int []arr,

int n)

{

Dictionary<int, int> hp =

new Dictionary<int, int>();

for (int i = 0; i < n; i++)

{

int key = arr[i];

if(hp.ContainsKey(key))

{

int freq = hp[key];

freq++;

hp[key] = freq;

}

else

hp.Add(key, 1);

}

int min_count = 0, res = -1;

foreach (KeyValuePair<int,

int> pair in hp)

{

if (min_count < pair.Value)

{

res = pair.Key;

min_count = pair.Value;

}

return res;

}

static void Main ()

{

int []arr = new int[]{40,50,30,40,50,30,30};

int n = arr.Length;

Console.Write(mostFrequent(arr, n));

}

Javascript

<script>

function mostFrequent(arr, n)

{

var hash = new Map();

for (var i = 0; i < n; i++)

{

if(hash.has(arr[i]))

hash.set(arr[i], hash.get(arr[i])+1)

else

hash.set(arr[i], 1)

}

var max_count = 0, res = -1;

hash.forEach((value,key) => {

if (max_count < value) {

res = key;

max_count = value;

}

});

return res;

}

var arr = [40,50,30,40,50,30,30];

var n = arr.length;

document.write( mostFrequent(arr, n));

</script>

Time Complexity: O(n)
Auxiliary Space: O(n)

An efficient solution to this problem can be to solve this problem by Moore’s voting Algorithm.

NOTE: THE ABOVE VOTING ALGORITHM ONLY WORKS WHEN THE MAXIMUM OCCURRING ELEMENT IS MORE THAN (SIZEOFARRAY/2) TIMES;

In this method, we will find the maximum occurred integer by counting the votes a number has.

C++

#include <iostream>

using namespace std;

int maxFreq(int *arr, int n) {

int res = 0;

int count = 1;

for(int i = 1; i < n; i++) {

if(arr[i] == arr[res]) {

count++;

} else {

count--;

}

if(count == 0) {

res = i;

count = 1;

}

return arr[res];

}

int main()

{

int arr[] = {40,50,30,40,50,30,30};

int n = sizeof(arr) / sizeof(arr[0]);

int freq = maxFreq(arr , n);

int count = 0;

for(int i = 0; i < n; i++) {

if(arr[i] == freq) {

count++;

}

cout <<"Element " << maxFreq(arr , n) << " occurs " << count << " times" << endl;;

return 0;

}

Java

import java.io.*;

class GFG

{

static int maxFreq(int []arr, int n)

{

int res = 0;

int count = 1;

for(int i = 1; i < n; i++) {

if(arr[i] == arr[res]) {

count++;

} else {

count--;

}

if(count == 0) {

res = i;

count = 1;

}

return arr[res];

}

public static void main (String[] args) {

int arr[] = {40,50,30,40,50,30,30};

int n = arr.length;

int freq = maxFreq(arr , n);

int count = 0;

for(int i = 0; i < n; i++) {

if(arr[i] == freq) {

count++;

}

System.out.println("Element " +maxFreq(arr , n) +" occurs " +count +" times" );

}

Python3

def maxFreq(arr, n):

res = 0

count = 1

for i in range(1, n):

if (arr[i] == arr[res]):

count += 1

else:

count -= 1

if (count == 0):

res = i

count = 1

return arr[res]

arr = [ 40, 50, 30, 40, 50, 30, 30 ]

n = len(arr)

freq = maxFreq(arr, n)

count = 0

for i in range (n):

if(arr[i] == freq):

count += 1

print("Element ", maxFreq(arr , n),

" occurs ", count, " times")

C#

using System;

class GFG

{

static int maxFreq(int []arr, int n)

{

int res = 0;

int count = 1;

for(int i = 1; i < n; i++) {

if(arr[i] == arr[res]) {

count++;

} else {

count--;

}

if(count == 0) {

res = i;

count = 1;

}

return arr[res];

}

public static void Main (String[] args) {

int []arr = {40,50,30,40,50,30,30};

int n = arr.Length;

int freq = maxFreq(arr , n);

int count = 0;

for(int i = 0; i < n; i++) {

if(arr[i] == freq) {

count++;

}

Console.Write("Element " +maxFreq(arr , n) +" occurs " +count +" times" );

}

Javascript

<script>

function maxFreq(arr, n) {

var res = 0;

var count = 1;

for (var i = 1; i < n; i++) {

if (arr[i] === arr[res]) {

count++;

} else {

count--;

}

if (count === 0) {

res = i;

count = 1;

}

return arr[res];

}

var arr = [40, 50, 30, 40, 50, 30, 30];

var n = arr.length;

var freq = maxFreq(arr, n);

var count = 0;

for (var i = 0; i < n; i++) {

if (arr[i] === freq) {

count++;

}

document.write(

"Element " + maxFreq(arr, n) + " occurs " +

count + " times" + "<br>"

);

</script>

Output

Element 30 occurs 3 times

Time Complexity: O(n)
Auxiliary Space: O(1)

Last Updated :
11 Jan, 2023

Like Article

Save Article

Источник

Поиск часто встречающихся элементов в массиве

Время на прочтение
5 мин

Количество просмотров 114K

Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?

К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву. Алгоритм Бойера-Мура — тех самых Бойера и Мура, что придумали намного более известный алгоритм поиска подстроки — проще всего представить следующим образом: на вечеринке собрались N людей, и на каждом по одному элементу из массива. Когда встречаются двое, у которых элементы разные, они присаживаются это обсудить. В конце концов останутся стоять только люди с одинаковыми элементами; очевидно, это тот самый элемент, который встречался больше N/2 раз.

Реализация алгоритма Бойера-Мура занимает всего несколько строк:

int* majority(int[] array, int N) {
  int confidence = 0; // количество людей, не нашедших пары и оставшихся стоять
  int* candidate = NULL; // последний человек, не нашедший пару -- 
                         // возможно, его элемент встречается чаще всего

  // проходим по массиву и усаживаем пары с разными элементами
  for (int i = 0; i<N; i++) {

    // если до сих пор все сидят, то следующему пока придётся постоять
    if (confidence == 0) {
      candidate = array+i;
      confidence++;
    }

    // иначе следующий либо садится с одним из стоящих,
    // либо будет стоять вместе с ними, если у него такой же элемент
    else if (*candidate == array[i])) 
      confidence++;
    else 
      confidence--;
  }

  return confidence > 0 ? candidate : NULL;
}

В конце мы получаем «наиболее вероятного кандидата» на присутствие в N/2 экземплярах: если такой элемент в массиве действительно существует, то он будет найден; если же такого элемента нет, то возможно, стоять останется просто какой-то бедолага, которому не хватило пары. Для более строгой реализации majority требуется пройти по массиву второй раз и проверить, действительно ли найденный элемент встречается требуемое количество раз.

Усложним задачу. Теперь в массиве длиной N надо найти элементы, которые повторяются больше N/3 раз — если есть два, то оба, если есть один, то один.

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

Идею прошлого алгоритма несложно обобщить и для троек: пусть люди с разными элементами рассаживаются по трое. Значит, в конце вечеринки останутся стоять люди максимум с двумя разными элементами. Если какой-то элемент встречался больше N/3 раз, значит человек с ним гарантированно останется стоять, ведь сидящих троек получится не больше N/3. Как и в прошлом случае, если искомые элементы существуют — то они будут найдены, но если их нет — то найтись может кто попало.

Код мало отличается от предыдущего: по-прежнему один проход по массиву и O(1) дополнительной памяти.

void majority(int[] array, int N, int** cand1, int** cand2) {
  int conf1 = 0, conf2 = 0; // количество стоящих людей с двумя элементами
  *cand1 = NULL; *cand2 = NULL; // два стоящих человека с разными элементами

  // проходим по массиву и усаживаем тройки с разными элементами
  for (int i = 0; i<N; i++) {

    // у следующего такой же элемент, как у стоящих? тогда встанет вместе с ними
    if (conf1 > 0 && **cand1 == array[i])
      conf1++;
    else if (conf2 > 0 && **cand2 == array[i])
      conf2++;
    else // может, стоят только с одним элементом, или вообще стоящих нет?
      if (conf1 == 0) {
        *cand1 = array+i;
        conf1++;
      } else if (conf2 == 0) {
        *cand2 = array+i;
        conf2++;
      }
    else { // стоят с двумя другими элементами, так что усаживаем всю тройку
      conf1--;
      conf2--;
    }
  }

  if(conf1 == 0) *cand1 = NULL;
  if(conf2 == 0) *cand2 = NULL;
}

Этот алгоритм опубликован в 1982 американскими учёными Джаядевом Мисрой и Дэвидом Грисом (Jayadev Misra & David Gries), и в их работе используется более скучная метафора — мешок с N числами, из которого они извлекают по 3 разных числа за каждую операцию. Кроме того, их псевдокод не похож ни на один понятный современному программисту язык. Мне больше понравилось объяснение их алгоритма в позапрошлогоднем конспекте лекций американского профессора Амита Чакрабарти.

В наиболее общей форме, когда в массиве длиной N надо найти элементы, которые повторяются больше N/k раз — придётся-таки воспользоваться словарём. Хранить в словаре мы будем только те элементы, с которыми люди стоят — т.е. не больше k-1 записей.

int[] majority(int[] array, int N, int k) {
  // словарь стоящих людей изначально пуст
  Dictionary<int,uint> candidates = new Dictionary<int,uint>{};

  // проходим по массиву и усаживаем группы по k
  for (int i = 0; i<N; i++) {

    // у следующего такой же элемент, как у стоящих? тогда встанет вместе с ними
    if (candidates.ContainsKey(array[i]))
      candidates[array[i]]++;
    else // может, стоят менее чем с k-1 элементами?
      if (candidates.Count < k - 1)
        candidates[array[i]] = 1;
    else // стоят с k-1 другими элементами, так что усаживаем всю группу
      foreach(int l in candidates.Keys)
        if (candidates[l]-- == 0)              // (**)
          candidates.Remove(l);                // (*)
  }

  return candidates.Keys.ToArray();
}

В этой наиболее общей форме алгоритма — по-прежнему один проход по массиву и O(k) дополнительной памяти. Если мы пользуемся для реализации словаря хэш-таблицей, а все записи в словаре свяжем в список — тогда общая сложность алгоритма останется линейной: строчка (*) с удалением записи из словаря выполняется самое большее N раз, ведь на каждой итерации основного цикла в словарь добавляется не больше одной записи. Читателям в качестве упражнения предлагается понять, почему строчка (**) не нарушает линейности алгоритма.

Таким образом наше устройство с маленькой памятью смогло бы общаться с одним пушистым зверьком, недавно препарированным хабраумельцами. Сигналы этого зверька имеют пять логических уровней: полагаем k=6, и получаем все пять уровней прямо на ходу, даже без сохранения сигнала в память. Нужно только обеспечить протоколом, чтобы все пять уровней встречались в сигнале одинаково часто.

Для алгоритма Мисры-Гриса упоминаются и другие применения. Например, можно следить в реальном времени за трафиком в сети, и если некий один хост потребляет непропорционально большую часть трафика — начинать расследование. Так же можно следить за кликами по баннерам, за финансовыми транзакциями, за потоком инструкций в моделируемом процессоре… В общем, всюду, где большое число повторений — подозрительная аномалия.

За оживление текста иллюстрациями надо благодарить Nitatunarabe

Источник

Число, чаще всего встречающееся в массиве

Просмотров 9.7к. Обновлено 15 октября 2021

Определить, какое число в массиве встречается чаще всего.

В программах ниже ищется только первое самое встречаемое число. Если есть другое число, которое встречается с такой же частотой как первое, то оно не определяется.

Будем записывать в переменную num найденный самый встречаемый элемент, а в переменную max_frq — количество раз, которое он встречается.

Будем по-очереди (в цикле) брать элементы массива с первого до предпоследнего и сравнивать его с элементами, стоящими после него. С элементами, стоящими впереди, сравнивать не надо, т.к. если там есть равный ему, то текущий элемент уже был учтен, и количество раз, какое он встречается в массиве, уже находилось. Последний элемент не с чем сравнивать, поэтому цикл идет до предпоследнего элемента.

В теле цикла переменной frq присваивается значение 1, т.е. вначале предполагается, что текущий элемент встречается 1 раз. Далее перебираются элементы, стоящие после текущего. Если значения совпадают, то переменная frq увеличивается на 1. После того, как посчитано количество раз, какое встречается элемент, переменная frq сравнивается с max_frq. Если frq больше, то перезаписываются значения max_frq и num.

Pascal

найти наиболее часто встречающееся число в массиве паскаль



const N = 15;

var

    arr: array[1..N] of byte;

    i, k, num, frq , max_frq: byte;

begin

    randomize;

    for i:=1 to N do begin

        arr[i] := random(20);

        write(arr[i],' ');

    end;

    writeln;
 
    num := arr[1];

    max_frq := 1;

    for i:=1 to N-1 do begin

        frq := 1;

        for k:=i+1 to N do

            if arr[i] = arr[k] then 

                frq := frq + 1;

        if frq > max_frq then begin

            max_frq := frq;

            num := arr[i];

        end;

    end;

 
    if max_frq > 1 then

        writeln(max_frq, ' раз(а) встречается число ', num)

    else

        writeln('Все элементы уникальны!');

end.





5 13 2 7 3 4 3 4 9 5 1 5 7 12 18 

3 раз(а) встречается число 5

Язык Си

найти наиболее часто встречающееся число в массиве c++



#include < stdio.h>

#define N 15

main() {

    short arr[N];

    short i, k, num, frq, max_frq;

    srand(time(NULL));

    for (i=0; i< N; i++) {

        arr[i] = rand() % 20;

        printf("%d ", arr[i]);

    }

    printf("n");
 
    num = arr[0];

    max_frq = 1;

    for (i=0; i < N-1; i++) {

        frq = 1;

        for (k = i+1; k< N; k++) 

            if (arr[i] == arr[k])

                frq += 1;

        if (frq > max_frq) {

            max_frq = frq;

            num = arr[i];

        }

    }

 
    if (max_frq > 1) 

        printf("%d раз(а) встречается число %dn", max_frq,num);

    else

        printf("Все элементы уникальны!n");

}





7 18 13 15 6 16 12 5 10 15 10 2 10 7 2 

3 раз(а) встречается число 10

Python

найти самый часто встречающийся элемент из массива python



from random import random

N = 15

arr = [0] * N

for i in range(N):

    arr[i] = int(random() * 20)

print(arr)
 
num = arr[0]

max_frq = 1

for i in range(N-1):

    frq = 1

    for k in range(i+1,N):

        if arr[i] == arr[k]:

            frq += 1

    if frq > max_frq:

        max_frq = frq

        num = arr[i]

 
if max_frq > 1:

    print(max_frq, 'раз(а) встречается число', num)

else:

    print('Все элементы уникальны')





[7, 18, 16, 18, 1, 11, 2, 16, 2, 4, 7, 7, 10, 17, 2]

3 раз(а) встречается число 7

КуМир



алг самое частое число

нач

  цел N = 15

  целтаб arr[1:N]

  цел i, k, num, frq, max_frq

  нц для i от 1 до N 

    arr[i] := irand(0,19)

    вывод arr[i], " "

  кц 

  вывод нс
 
  num := arr[1]

  max_frq := 1

  нц для i от 1 до N-1

    frq := 1

    нц для k от i+1 до N

      если arr[i] = arr[k] то

        frq := frq + 1

      все

    кц

    если frq > max_frq то

      max_frq := frq

      num := arr[i]

    все

  кц

 
  если max_frq > 1 то

    вывод max_frq," раз(а) встречается число ",num

   иначе

    вывод "Все элементы уникальны"

  все

кон





1 10 11 0 11 9 18 13 6 18 0 12 18 16 14 

3 раз(а) встречается число 18

Basic-256



N = 15

dim arr(N)

for i=0 to N-1 

	arr[i] = int(rand * 20)

	print arr[i] + " ";

next i

print
 
num = arr[0]

max_frq = 1

for i=0 to N-2

	frq = 1

	for k=i+1 to N-1

		if arr[i] = arr[k] then

			frq = frq + 1

		endif

	next k

	if frq > max_frq then

		max_frq = frq

		num = arr[i]

	endif

next i

 
print max_frq + " раз(а) встречается число " + num





5 13 19 7 13 17 18 4 10 15 15 18 15 7 14 

3 раз(а) встречается число 15

Источник

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

Я делал вот так. Ввод данных с клавиатуры:

n = int(input())
new = list(map(int, input().split()))

Сопоставление каждому элементу из массива его частоты (количество вхождений):

mydict = {}
for elem in new:
    mydict[elem] = 0
for elem in new:
    mydict[elem] = mydict[elem] + 1

А как быть дальше? Можно ли за линию вытащить наиболее встречающийся элемент с наибольшем значением?

задан 25 фев 2022 в 18:33

Дополнение к вашему коду. Вы бежите по парам элемент/счётчик и выбираете из них самую большую, сперва по счётчику, затем по значению (для этого lambda):

item, count = max(mydict.items(), key=lambda p: p[::-1])

Ваш код можно доработать используя collections.Counter:

import collections


input() # skip line
c = collections.Counter(map(int, input().split()))
item, count = max(c.items(), key=lambda p: p[::-1])
print(item, count)

ответ дан 25 фев 2022 в 19:23

from collections import Counter


def main():
    counter = Counter()

    list_integer = list(map(int, input("Введите числа через пробел-> ").split()))

    for integer in list_integer:
        counter[integer] += 1

    often_meets_number = max(counter, key=counter.get)
    print(f"Часто встречается число: {often_meets_number}")

if __name__ == '__main__':
    main()

ответ дан 25 фев 2022 в 19:00

АлександрАлександр

2,9852 золотых знака14 серебряных знаков21 бронзовый знак

или еще так:

n = int(input())
new = list(map(int, input().split()))

res = max(sorted(new, reverse=True), key=lambda x: new.count(x))

ответ дан 26 фев 2022 в 7:58

SergFSMSergFSM

5,6501 золотой знак6 серебряных знаков17 бронзовых знаков

Вполне можно за линию найти этот максимум. Сорри что на С++ но не думаю что будет сложно перевести этот код на питон.

int dupls_max(const std::vector<int>& v)
{
    int max_el = *std::max_element(v.begin(), v.end());
    std::vector<int> counts(max_el + 1);    
    for (int i=0; i < v.size(); ++i)
    {
        counts[v[i]]++;
    }
    int dupls_max = 0;
    for (int i=0; i < v.size(); ++i)
    {
        if (counts[v[i]] > 1)
        {
            if (v[i] > dupls_max)
                dupls_max = v[i];
        }        
    }    
    return dupls_max;
}

Тоесть дальше банально ищется максимум с предпроверкой на частоту появления.

ответ дан 11 мая 2022 в 21:40

ampawdampawd

3,6821 золотой знак14 серебряных знаков30 бронзовых знаков

Источник

python массивы

Ответы

Ivan Mamtsev

25 июля 2022

Наиболее встречающийся элемент массива проще всего найти с помощью Counter

from collections import Counter

l = ['a', 'b', 'a', 'c', 'c', 'a']
Counter(l).most_common(1) # [('a', 3)]

0

0

Добавьте ваш ответ

C++

Java

Python3

C#

Javascript

C++

C

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Поиск часто встречающихся элементов в массиве

Число, чаще всего встречающееся в массиве

Pascal

Язык Си

Python

КуМир

Basic-256

Рекомендуемые курсы

Похожие вопросы

Не пропустите также: