در این مطلب، روش نوشتن برنامه‌ای که عناصر متداول در آرایه را پیدا کند، آموزش داده شده است. فرض می‌شود که یک آرایه داده شده و هدف، پیدا کردن متداول‌ترین عنصر در آن است. همچنین، اگر چند عنصر وجود دارند که تعداد تکرار آن‌ها با هم برابر و از سایر عناصر بیشتر است، هدف، چاپ کردن همه آن‌ها است. برای درک بهتر مطلب، مثال‌های زیر قابل توجه هستند.

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

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

یک راهکار ساده برای این مسئله، اجرای دو حلقه به صورت هم‌زمان است. حلقه بیرونی همه عناصر را یکی یکی انتخاب می‌کند. حلقه درونی همه تکرارهای عنصر انتخاب شده را پیدا می‌کند و با حداکثر تکرار مشخص شده تا آن لحظه، مقایسه می‌کند. پیچیدگی زمانی این روش، از درجه O(n²)‎ است. یک راهکار بهتر، استفاده از مرتب‌سازی است. ابتدا آرایه مرتب و سپس، پیمایش خطی در آرایه انجام می‌شود.

پیاده‌سازی در ++C

// CPP program to find the most frequent element 
// in an array. 
#include <bits/stdc++.h> 
using namespace std; 
  
int mostFrequent(int arr[], int n) 
{ 
    // Sort the array 
    sort(arr, arr + n); 
  
    // find the max frequency using linear traversal 
    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 { 
            if (curr_count > max_count) { 
                max_count = curr_count; 
                res = arr[i - 1]; 
            } 
            curr_count = 1; 
        } 
    } 
  
    // If last element is most frequent 
    if (curr_count > max_count) 
    { 
        max_count = curr_count; 
        res = arr[n - 1]; 
    } 
  
    return res; 
} 
  
// driver program 
int main() 
{ 
    int arr[] = { 1, 5, 2, 1, 3, 2, 1 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << mostFrequent(arr, n); 
    return 0; 
}

پیاده‌سازی در جاوا

//Java program to find the most frequent element 
//in an array 
import java.util.*; 
  
class GFG { 
      
    static int mostFrequent(int arr[], int n) 
    { 
          
        // Sort the array 
        Arrays.sort(arr); 
          
        // find the max frequency using linear 
        // traversal 
        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 
            { 
                if (curr_count > max_count) 
                { 
                    max_count = curr_count; 
                    res = arr[i - 1]; 
                } 
                curr_count = 1; 
            } 
        } 
      
        // If last element is most frequent 
        if (curr_count > max_count) 
        { 
            max_count = curr_count; 
            res = arr[n - 1]; 
        } 
      
        return res; 
    } 
      
    // Driver program 
    public static void main (String[] args) { 
          
        int arr[] = {1, 5, 2, 1, 3, 2, 1}; 
        int n = arr.length; 
          
        System.out.println(mostFrequent(arr,n)); 
          
    } 
} 
  
// This code is contributed by Akash Singh.

پیاده‌سازی در پایتون ۳

# Python3 program to find the most  
# frequent element in an array. 
  
def mostFrequent(arr, n): 
  
    # Sort the array 
    arr.sort() 
  
    # find the max frequency using 
    # linear traversal 
    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 : 
            if (curr_count > max_count):  
                max_count = curr_count 
                res = arr[i - 1] 
              
            curr_count = 1
      
    # If last element is most frequent 
    if (curr_count > max_count): 
      
        max_count = curr_count 
        res = arr[n - 1] 
      
    return res 
  
# Driver Code 
arr = [1, 5, 2, 1, 3, 2, 1]  
n = len(arr) 
print(mostFrequent(arr, n)) 
  
# This code is contributed by Smitha Dinesh Semwal.

پیاده‌سازی در سی‌شارپ

// C# program to find the most  
// frequent element in an array 
using System; 
  
class GFG { 
      
    static int mostFrequent(int []arr, int n) 
    { 
          
        // Sort the array 
        Array.Sort(arr); 
          
        // find the max frequency using  
        // linear traversal 
        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
            { 
                if (curr_count > max_count) 
                { 
                    max_count = curr_count; 
                    res = arr[i - 1]; 
                } 
                curr_count = 1; 
            } 
        } 
      
        // If last element is most frequent 
        if (curr_count > max_count) 
        { 
            max_count = curr_count; 
            res = arr[n - 1]; 
        } 
      
        return res; 
    } 
      
    // Driver code 
    public static void Main ()  
    { 
          
        int []arr = {1, 5, 2, 1, 3, 2, 1}; 
        int n = arr.Length; 
          
        Console.WriteLine(mostFrequent(arr,n)); 
          
    } 
} 
  
// This code is contributed by vt_m.

پیاده‌سازی در پی‌اچ‌پی

<?php 
// PHP program to find the 
// most frequent element 
// in an array. 
  
function mostFrequent( $arr, $n) 
{ 
      
    // Sort the array 
    sort($arr); 
    sort($arr , $n); 
  
    // find the max frequency  
    // using linear traversal 
    $max_count = 1;  
    $res = $arr[0];  
    $curr_count = 1; 
    for ($i = 1; $i < $n; $i++)  
    { 
        if ($arr[$i] == $arr[$i - 1]) 
            $curr_count++; 
        else 
        { 
            if ($curr_count > $max_count) 
            { 
                $max_count = $curr_count; 
                $res = $arr[$i - 1]; 
            } 
            $curr_count = 1; 
        } 
    } 
  
    // If last element  
    // is most frequent 
    if ($curr_count > $max_count) 
    { 
        $max_count = $curr_count; 
        $res = $arr[$n - 1]; 
    } 
  
    return $res; 
} 
  
// Driver Code 
{ 
    $arr = array(1, 5, 2, 1, 3, 2, 1); 
    $n = sizeof($arr) / sizeof($arr[0]); 
    echo mostFrequent($arr, $n); 
    return 0; 
} 
  
// This code is contributed by nitin mittal 
?>

خروجی قطعه کد بالا، به صورت زیر است.

۱

پیچیدگی زمانی این روش از درجه O(n Log n)‎ و پیچیدگی فضایی آن از درجه O(1)‎ است. یک راهکار موثر، استفاده از «درهم‌سازی» (Hashing) است. یک جدول درهم‌سازی ساخته می‌شود و عناصر جدول و تعداد تکرار آن‌ها به عنوان جفت کلید مقدار ذخیره می‌شود. در نهایت، پیمایش در جدول هش انجام و کلیدی با بیشینه مقدار، چاپ می‌شود.

پیاده‌سازی راهکار بهینه در سی‌پلاس‌پلاس

// CPP program to find the most frequent element 
// in an array. 
#include <bits/stdc++.h> 
using namespace std; 
  
int mostFrequent(int arr[], int n) 
{ 
    // Insert all elements in hash. 
    unordered_map<int, int> hash; 
    for (int i = 0; i < n; i++) 
        hash[arr[i]]++; 
  
    // find the max frequency 
    int max_count = 0, res = -1; 
    for (auto i : hash) { 
        if (max_count < i.second) { 
            res = i.first; 
            max_count = i.second; 
        } 
    } 
  
    return res; 
} 
  
// driver program 
int main() 
{ 
    int arr[] = { 1, 5, 2, 1, 3, 2, 1 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << mostFrequent(arr, n); 
    return 0; 
}

پیاده‌سازی راهکار بهینه در جاوا

//Java program to find the most frequent element 
//in an array 
import java.util.HashMap; 
import java.util.Map; 
import java.util.Map.Entry; 
  
class GFG { 
      
    static int mostFrequent(int arr[], int n) 
    { 
          
        // Insert all elements in hash 
        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); 
            } 
        } 
          
        // find max frequency. 
        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; 
    } 
      
    // Driver code 
    public static void main (String[] args) { 
          
        int arr[] = {1, 5, 2, 1, 3, 2, 1}; 
        int n = arr.length; 
          
        System.out.println(mostFrequent(arr, n)); 
    } 
} 
  
// This code is contributed by Akash Singh. 

پیاده‌سازی راهکار بهینه در پایتون ۳

# Python3 program to find the most  
# frequent element in an array. 
import math as mt 
  
def mostFrequent(arr, n): 
  
    # Insert all elements in Hash. 
    Hash = dict() 
    for i in range(n): 
        if arr[i] in Hash.keys(): 
            Hash[arr[i]] += 1
        else: 
            Hash[arr[i]] = 1
  
    # find the max frequency 
    max_count = 0
    res = -1
    for i in Hash:  
        if (max_count < Hash[i]):  
            res = i 
            max_count = Hash[i] 
          
    return res 
  
# Driver Code 
arr = [ 1, 5, 2, 1, 3, 2, 1]  
n = len(arr) 
print(mostFrequent(arr, n)) 
  
# This code is contributed  
# by Mohit kumar 29

پیاده‌سازی راهکار بهینه در سی‌شارپ

// C# program to find the most  
// frequent element in an array 
using System; 
using System.Collections.Generic; 
  
class GFG 
{ 
    static int mostFrequent(int []arr,  
                            int n) 
    { 
        // Insert all elements in hash 
        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); 
        } 
          
        // find max frequency. 
        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; 
    } 
      
    // Driver code 
    static void Main () 
    { 
        int []arr = new int[]{1, 5, 2,  
                              ۱, ۳, ۲, ۱}; 
        int n = arr.Length; 
          
        Console.Write(mostFrequent(arr, n)); 
    } 
} 
  
// This code is contributed by 
// Manish Shaw(manishshaw1)

خروجی قطعه کدهای بالا، به صورت زیر است.

۱

پیچیدگی زمانی و فضایی این روش، هر دو از درجه O(n)‎ هستند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده