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

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(n2) 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

Источник

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

Просмотров 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

Источник

Скорее всего наиболее быстрым методом решения этой задачи будет сортировка (как сделали вы и как было показано в ответе @Harry). Если нельзя модифицировать исходный массив, то для подсчета проще всего сделать его копию.

Что касается хэширования, то эта процедура программируется на Си достаточно просто (см. ниже), однако имеет много подводных камней, связанных с распределением значений массива. В случае неудачной для конкретного распределения хэш-функции (например, для примера ниже это случай, когда в массиве размером 1000000 все элементы разные, но их младшие 20 бит одинаковы) мы получим огромное время вместе с огромным (опять же, для примера ниже в 4 раза больше размера исходного массива) расходом памяти.

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

Когда диапазон значений элементов массива разумно мал (скажем, не превышает 1000000 (но для маленьких массивов разумно будет уменьшить этот диапазон до величины сопоставимой с размером массива)), то вместо «настоящего» хэширования для подсчета частот можно использовать массив счетчиков, индексируемый элементами массива.

Получим что-то такое:

  int ar_size, // размер массива
      size,    // диапазон
      from;    // нижняя граница

  int *ar = malloc(sizeof(int) * ar_size);
  for (int i = 0; i < ar_size; i++) // заполним массив как в коде вопроса 
      ar[i] = random() % size + from; 

  if (size < LSIZE) {  // LSIZE это упомянутая разумная граница
    int *cnt = calloc(sizeof(int), size);

    // установим счетчики частот элементов массива
    for (int i = 0; i < ar_size; i++) {
      int iv = ar[i] - from;
      cnt[iv]++;
    }

    // тривиальный поиск максимума
    int vmax = cnt[0], ivmax = 0;
    for (int i = 1; i < size; i++)
      if (cnt[i] > vmax) 
        vmax = cnt[i], ivmax = i;

    free(cnt);

    printf("max freq %d for %dn", vmax, ivmax + from);
  }

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

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

Для примера запрограммируем разрешение коллизий методом цепочек. В нем синонимы (т.е. разные числа, адресующие одно и то же место в таблице) помещаются в односвязный список. Обычно каждый элемент такого списка выделяется отдельным вызовом malloc(). В Linux x86-64 минимальный размер, выделяемый malloc это 32 байта. Поскольку мы хэшируем элементы массива int известного размера, то попробуем немного поэкономить память, выделяя под элемент цепочки коллизий всего 12 байт. Этого можно добиться, если вместо указателя (размер 8 байт) для адресации следующего элемента цепочки коллизий использовать индекс в массиве, в котором и размещать все эти элементы.

Получим такие структуры данных:

// элемент хэш таблицы, синонимы образуют список
struct htab_item {
  int val,  // число из массива `ar[]`
      cnt,  // счетчик 
      next; // индекс следующего элемента списка
};

struct htab {
  int hisize,   //  размер массива `.hindx`  (размер = ar_size, но его можно выбрать и другим)
      dsize,    //  размер массива `tabdata` (размер = ar_size)
      fdata;    //  первый свободный `htab_item` in `tabdata`
  int *hindx;   //  индексы начала цепочек коллизий в массиве `tabdata`
  struct htab_item *tabdata;
};

// функция для добавления нового элемента 
// возвращает его индекс в `tabdata`
int add_ht_item (struct htab *h, int v) {
  h->tabdata[h->fdata].val = v;
  h->tabdata[h->fdata].cnt = 1;
  h->tabdata[h->fdata].next = -1; // -1 означает, что это последний элемент цепочки коллизий

  return h->fdata++;
}

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

Ну, и код для заполнения хэш-таблицы и поиска наиболее часто встречающегося числа

struct htab ht = {ar_size, ar_size, 0,
                  malloc(ar_size * sizeof(int)),
                  calloc(ar_size, sizeof(struct htab_item))};

// инициализируем индексы свободных элементов таблицы числом -1
memset(ht.hindx, -1, ht.hisize * sizeof(int));

for (int i = 0; i < ar_size; i++) {
  unsigned int v0 = ar[i];
  int htix = v0 % ht.hisize;
  if (ht.hindx[htix] == -1)
    ht.hindx[htix] = add_ht_item(&ht, ar[i]);
  else {
    for (int j = ht.hindx[htix];;j = ht.tabdata[j].next) {
      if (ht.tabdata[j].val == ar[i]) {
        ht.tabdata[j].cnt++;
        break;
      }
      if (ht.tabdata[j].next == -1) {
        ht.tabdata[j].next = add_ht_item(&ht, ar[i]);
        break;
      }
    }
  }
}

int vmax = ht.tabdata[0].cnt, ivmax = 0;
for (int i = 1; i < ht.fdata; i++)
  if (ht.tabdata[0].cnt > vmax)
    vmax = ht.tabdata[0].cnt, ivmax = i;


printf("max freq %d for %dn", vmax, ht.tabdata[ivmax].val);

free(ht.hindx);
free(ht.tabdata);

Если что-то не понятно или интересно рассмотреть варианты, не стесняйтесь, спрашивайте в комментариях.

Источник
  • python массивы

Ответы

Аватар пользователя Ivan Mamtsev

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

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

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

курс

Python: Numpy-массивы

12 часов

Старт в любое время

курс

Python: Введение в ООП

12 часов

Старт в любое время

курс

Python: Разработка на фреймворке Django

21 час

Старт в любое время

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

  • python массивы

Как выбрать последний элемент массива python


01 ноября 2021

1

ответ

  • python массивы

Как перемешать элементы массива python


01 ноября 2021

1

ответ

  • python массивы

Как посчитать количество элементов в массиве python


01 ноября 2021

2

ответа

  • python массивы

Как убрать одинаковые элементы массива python


01 ноября 2021

1

ответ

Источник
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <stdio.h> 
#include <conio.h> 
 
const int N = 10;
int main()
{     
 int mass[N]={3, 3, 2, 2, 1, 1, 7, 7, 9, 9}; // Обявляем массив.
 int list[N]; /* Обявляем массив, куда будут заносится равные, но наиб.  встречающиеся элементы.
                 Например, если задать массив из 5 элементов - 2, 2, 3, 3, 1, то вывести 2 и 3.
              */
 int i, j, count, maxcount, num, len; 
 printf("n Massiv iz chisel ot 1 do 10: n");
  for(i=0; i<N; i++)
  { printf("n Massiv[%d] = %d. ", i, mass[i]); }
  
 len=0; maxcount=1; num=0; // Устанавливаем значения трех переменных по умолчанию.
   for (i=0; i<N; i++) // Перебираем все элементы массива.
    { count=0; // Счетчик в 0.      
       for (j=i; j<N; j++) // Перебираем все элементы от i до конца.
        if (mass[i] == mass[j]) // Если элемент [i] совпадает с одним из последующих [j],
           { count++; } // то увеличиваем значение счетчика.
        if (count==maxcount) // Если очередное число встречается maxcount раз, 
         { list[len]=i; // То занесём его в список.
            len++; } // Увеличиваем значение переменной.
        if (count > maxcount) // Если число больше максимального,
         { maxcount = count; // тогда оно максимальное.
           num = i;  //  Присаваеиваем элемент массива в новую переменную             
           len=1; // Разрушаем прежний список...
           list[0]=i; } // и формируем новый.
    }        
      printf("n n Povtor. chisla:");
     for(i=0; i<len; i++)  
      { printf(" %d.", mass[list[i]]); }  // Выводим значения часто повторяющийся элементов.
  
 getch(); 
 return 0;
}
Источник

Понравилась статья? Поделить с друзьями:
  • Киберпанк 2077 как найти подсказки на записи
  • Видео как найти все подковы
  • Как найти работу по резюме бесплатно
  • Как исправить цифры в диаграмме в ворде
  • Как найти косинус румба калькулятор