算法设计：数组中最少的元素

2021年4月18日19:21:43 发表评论 759 次浏览

本文概述

给定一个数组, 在其中找到最不频繁的元素。如果有多个元素出现的次数最少, 请打印其中的任何一个。

例子 ：

Input : arr[] = {1, 3, 2, 1, 2, 2, 3, 1}
Output : 3
3 appears minimum number of times in given
array.

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

一种简单的解决方案是要运行两个循环。外循环一一挑选所有元素。内循环找到所拾取元素的频率, 并与到目前为止的最小值进行比较。该解决方案的时间复杂度为O(n2)

一种更好的解决方案是要进行排序。我们首先对数组进行排序, 然后线性遍历数组。

C++

//CPP program to find the least frequent element
//in an array.
#include <bits/stdc++.h>
using namespace std;
  
int leastFrequent( int arr[], int n)
{
     //Sort the array
     sort(arr, arr + n);
  
     //find the min frequency using linear traversal
     int min_count = n+1, res = -1, curr_count = 1;
     for ( int i = 1; i <n; i++) {
         if (arr[i] == arr[i - 1])
             curr_count++;
         else {
             if (curr_count <min_count) {
                 min_count = curr_count;
                 res = arr[i - 1];
             }
             curr_count = 1;
         }
     }
   
     //If last element is least frequent
     if (curr_count <min_count)
     {
         min_count = curr_count;
         res = arr[n - 1];
     }
  
     return res;
}
  
//driver program
int main()
{
     int arr[] = {1, 3, 2, 1, 2, 2, 3, 1};
     int n = sizeof (arr) /sizeof (arr[0]);
     cout <<leastFrequent(arr, n);
     return 0;
}

Java

//Java program to find the least frequent element
//in an array.
import java.io.*;
import java.util.*;
  
class GFG {
      
     static int leastFrequent( int arr[], int n)
     {
          
         //Sort the array
         Arrays.sort(arr);
      
         //find the min frequency using 
         //linear traversal
         int min_count = n+ 1 , res = - 1 ;
         int curr_count = 1 ;
          
         for ( int i = 1 ; i <n; i++) {
             if (arr[i] == arr[i - 1 ])
                 curr_count++;
             else {
                 if (curr_count <min_count) {
                     min_count = curr_count;
                     res = arr[i - 1 ];
                 }
                  
                 curr_count = 1 ;
             }
         }
      
         //If last element is least frequent
         if (curr_count <min_count)
         {
             min_count = curr_count;
             res = arr[n - 1 ];
         }
      
         return res;
     }
      
     //driver program
     public static void main(String args[])
     {
         int arr[] = { 1 , 3 , 2 , 1 , 2 , 2 , 3 , 1 };
         int n = arr.length;
         System.out.print(leastFrequent(arr, n));
          
     }
}
  
/*This code is contributed by Nikita Tiwari.*/

Python3

# Python 3 program to find the least
# frequent element in an array.
  
  
def leastFrequent(arr, n) :
  
     # Sort the array
     arr.sort()
   
     # find the min frequency using
     # linear traversal
     min_count = n + 1
     res = - 1
     curr_count = 1
     for i in range ( 1 , n) :
         if (arr[i] = = arr[i - 1 ]) :
             curr_count = curr_count + 1
         else :
             if (curr_count <min_count) :
                 min_count = curr_count
                 res = arr[i - 1 ]
              
             curr_count = 1
              
    
     # If last element is least frequent
     if (curr_count <min_count) :
         min_count = curr_count
         res = arr[n - 1 ]
      
     return res
      
   
# Driver program
arr = [ 1 , 3 , 2 , 1 , 2 , 2 , 3 , 1 ]
n = len (arr)
print (leastFrequent(arr, n))
  
  
# This code is contributed
# by Nikita Tiwari.

C#

//C# program to find the least 
//frequent element in an array.
using System;
  
class GFG {
      
     static int leastFrequent( int [] arr, int n)
     {
         //Sort the array
         Array.Sort(arr);
      
         //find the min frequency 
         //using linear traversal
         int min_count = n + 1, res = -1;
         int curr_count = 1;
          
         for ( int i = 1; i <n; i++) 
         {
             if (arr[i] == arr[i - 1])
                 curr_count++;
             else 
             {
                 if (curr_count <min_count)
                 {
                     min_count = curr_count;
                     res = arr[i - 1];
                 }
                  
                 curr_count = 1;
             }
         }
      
         //If last element is least frequent
         if (curr_count <min_count)
         {
             min_count = curr_count;
             res = arr[n - 1];
         }
      
         return res;
     }
      
     //Driver code
     static public void Main ()
     {
         int [] arr = {1, 3, 2, 1, 2, 2, 3, 1};
         int n = arr.Length; 
          
         //Function calling
         Console.Write(leastFrequent(arr, n));
     }
}
  
//This code is contributed by Shrikant13

的PHP

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

输出如下：

3

时间复杂度：O(n Log n)

辅助空间：O(1)

一个有效的解决方案是使用哈希。我们创建一个哈希表, 并将元素及其频率计数存储为键值对。最后, 我们遍历哈希表并打印具有最小值的键。

C++

//CPP program to find the least frequent element
//in an array.
#include <bits/stdc++.h>
using namespace std;
  
int leastFrequent( 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 min frequency
     int min_count = n+1, res = -1;
     for ( auto i : hash) {
         if (min_count>= i.second) {
             res = i.first;
             min_count = i.second;
         }
     }
  
     return res;
}
  
//driver program
int main()
{
     int arr[] = {1, 3, 2, 1, 2, 2, 3, 1};
     int n = sizeof (arr) /sizeof (arr[0]);
     cout <<leastFrequent(arr, n);
     return 0;
}

Java

//Java program to find the least frequent element
//in an array
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
  
class GFG {
      
     static int leastFrequent( int arr[], int n)
     {
          
         //Insert all elements in hash.
         Map<Integer, Integer> count = 
                    new HashMap<Integer, Integer>();
                     
         for ( int i = 0 ; i <n; i++)
         {
             int key = arr[i];
             if (count.containsKey(key))
             {
                 int freq = count.get(key);
                 freq++;
                 count.put(key, freq);
             }
             else
                 count.put(key, 1 );
         }
          
         //find min frequency.
         int min_count = n+ 1 , res = - 1 ;
         for (Entry<Integer, Integer> val : count.entrySet())
         {
             if (min_count>= val.getValue())
             {
                 res = val.getKey();
                 min_count = val.getValue();
             }
         }
          
         return res;
     }
      
     //driver program
     public static void main (String[] args) {
          
         int arr[] = { 1 , 3 , 2 , 1 , 2 , 2 , 3 , 1 };
         int n = arr.length;
          
         System.out.println(leastFrequent(arr, n));
     }
}
  
//This code is contributed by Akash Singh.

Python3

# Python3 program to find the most 
# frequent element in an array.
import math as mt
  
def leastFrequent(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
     min_count = n + 1
     res = - 1
     for i in Hash : 
         if (min_count> = Hash [i]): 
             res = i
             min_count = Hash [i]
          
     return res
  
# Driver Code
arr = [ 1 , 3 , 2 , 1 , 2 , 2 , 3 , 1 ] 
n = len (arr)
print (leastFrequent(arr, n))
  
# This code is contributed by
# mohit kumar 29

C#

//C# program to find the 
//least frequent element 
//in an array.
using System;
using System.Collections.Generic;
  
class GFG
{
     static int leastFrequent( int []arr, int n)
     {
         //Insert all elements in hash.
         Dictionary<int , int> count = 
                         new Dictionary<int , int>();
         for ( int i = 0; i <n; i++)
         {
             int key = arr[i];
             if (count.ContainsKey(key))
             {
                 int freq = count[key];
                 freq++;
                 count[key] = freq;
             }
             else
                 count.Add(key, 1);
         }
          
         //find the min frequency
         int min_count = n + 1, res = -1;
         foreach (KeyValuePair<int , int> pair in count)
         {
             if (min_count>= pair.Value)
             {
                 res = pair.Key;
                 min_count = pair.Value;
             }
         } 
         return res;
     }
      
     //Driver Code
     static void Main()
     {
         int []arr = new int []{1, 3, 2, 1, 2, 2, 3, 1};
         int n = arr.Length;
         Console.Write(leastFrequent(arr, n));
     }
}
  
//This code is contributed by 
//Manish Shaw(manishshaw1)

输出如下：

3

时间复杂度：O(n)

辅助空间：O(n)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: