算法设计：如何计算下一个更高频率的元素？

2021年4月1日15:52:24 发表评论 943 次浏览

本文概述

给定一个数组，对于每个元素，找出最右边最近且频率大于当前元素的元素的值。如果不存在一个位置的答案，则将值设置为'-1'。

例子：

Input : a[] = [1, 1, 2, 3, 4, 2, 1] 
Output : [-1, -1, 1, 2, 2, 1, -1]
Explanation:
Given array a[] = [1, 1, 2, 3, 4, 2, 1] 
Frequency of each element is: 3, 3, 2, 1, 1, 2, 3
Lets calls Next Greater Frequency element as NGF
1. For element a[0] = 1 which has a frequency = 3, As it has frequency of 3 and no other next element 
   has frequency more than 3 so  '-1'
2. For element a[1] = 1 it will be -1 same logic 
   like a[0]
3. For element a[2] = 2 which has frequency = 2, NGF element is 1 at position = 6  with frequency 
   of 3 > 2
4. For element a[3] = 3 which has frequency = 1, NGF element is 2 at position = 5 with frequency 
   of 2 > 1
5. For element a[4] = 4 which has frequency = 1, NGF element is 2 at position = 5 with frequency 
   of 2 > 1
6. For element a[5] = 2 which has frequency = 2, NGF element is 1 at position = 6 with frequency
   of 3 > 2
7. For element a[6] = 1 there is no element to its 
   right, hence -1 

Input : a[] = [1, 1, 1, 2, 2, 2, 2, 11, 3, 3]
Output : [2, 2, 2, -1, -1, -1, -1, 3, -1, -1]

天真的方法：

一种简单的哈希技术是在索引用于存储每个元素的频率时使用值。假设创建一个列表, 以存储数组中每个数字的频率。 (需要单遍历)。现在使用两个循环。

外循环一个接一个地选取所有元素。

内循环查找其频率大于当前元素频率的第一个元素。

如果找到更高频率的元素, 则打印该元素, 否则打印-1。

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

高效的方法: 我们可以使用哈希和堆栈数据结构来有效地解决许多情况。一种简单的哈希技术是将值用作索引, 将每个元素的频率用作值。我们使用堆栈数据结构来存储元素在数组中的位置。

1)创建一个列表, 使用值作为索引来存储每个元素的频率。
2)将第一个元素的位置推入堆栈。
3)逐个拾取其余元素的位置, 然后循环执行以下步骤。
......a)将当前元素的位置标记为" i"。
......b)如果由堆栈顶部指向的元素的频率大于当前元素的频率, 则将当前位置i推入堆栈……。
c)如果由堆栈顶部指向的元素的频率小于当前元素的频率, 并且堆栈不为空, 则执行以下步骤：
......i)继续弹出堆栈
......ii)如果如果步骤c中的条件失败, 则将当前位置i推入堆栈.
4)步骤3中的循环结束后, 从堆栈中弹出所有元素, 并打印-1, 因为不存在下一个更高频率的元素。

下面是上述问题的实现。

C ++

// C++ program of Next Greater Frequency Element
#include <iostream>
#include <stack>
#include <stdio.h>
 
using namespace std;
 
/*NFG function to find the next greater frequency
element for each element in the array*/
void NFG( int a[], int n, int freq[])
{
 
     // stack data structure to store the position
     // of array element
     stack< int > s;
     s.push(0);
 
     // res to store the value of next greater
     // frequency element for each element
     int res[n] = { 0 };
     for ( int i = 1; i < n; i++) {
         /* If the frequency of the element which is
             pointed by the top of stack is greater
             than frequency of the current element
             then push the current position i in stack*/
 
         if (freq[a[s.top()]] > freq[a[i]])
             s.push(i);
         else {
             /*If the frequency of the element which
             is pointed by the top of stack is less
             than frequency of the current element, then
             pop the stack and continuing popping until
             the above condition is true while the stack
             is not empty*/
 
             while (freq[a[s.top()]] < freq[a[i]]
                    && !s.empty()) {
 
                 res[s.top()] = a[i];
                 s.pop();
             }
             //  now push the current element
             s.push(i);
         }
     }
 
     while (!s.empty()) {
         res[s.top()] = -1;
         s.pop();
     }
     for ( int i = 0; i < n; i++) {
         // Print the res list containing next
         // greater frequency element
         cout << res[i] << " " ;
     }
}
 
// Driver code
int main()
{
 
     int a[] = { 1, 1, 2, 3, 4, 2, 1 };
     int len = 7;
     int max = INT16_MIN;
     for ( int i = 0; i < len; i++) {
         // Getting the max element of the array
         if (a[i] > max) {
             max = a[i];
         }
     }
     int freq[max + 1] = { 0 };
 
     // Calculating frequency of each element
     for ( int i = 0; i < len; i++) {
         freq[a[i]]++;
     }
 
     // Function call
     NFG(a, len, freq);
     return 0;
}

Java

// Java program of Next Greater Frequency Element
import java.util.*;
 
class GFG {
 
     /*NFG function to find the next greater frequency
     element for each element in the array*/
     static void NFG( int a[], int n, int freq[])
     {
 
         // stack data structure to store the position
         // of array element
         Stack<Integer> s = new Stack<Integer>();
         s.push( 0 );
 
         // res to store the value of next greater
         // frequency element for each element
         int res[] = new int [n];
         for ( int i = 0 ; i < n; i++)
             res[i] = 0 ;
 
         for ( int i = 1 ; i < n; i++) {
             /* If the frequency of the element which is
                 pointed by the top of stack is greater
                 than frequency of the current element
                 then push the current position i in stack*/
 
             if (freq[a[s.peek()]] > freq[a[i]])
                 s.push(i);
             else {
                 /*If the frequency of the element which
                 is pointed by the top of stack is less
                 than frequency of the current element, then
                 pop the stack and continuing popping until
                 the above condition is true while the stack
                 is not empty*/
 
                 while (freq[a[s.peek()]] < freq[a[i]]
                        && s.size() > 0 ) {
                     res[s.peek()] = a[i];
                     s.pop();
                 }
 
                 // now push the current element
                 s.push(i);
             }
         }
 
         while (s.size() > 0 ) {
             res[s.peek()] = - 1 ;
             s.pop();
         }
 
         for ( int i = 0 ; i < n; i++) {
             // Print the res list containing next
             // greater frequency element
             System.out.print(res[i] + " " );
         }
     }
 
     // Driver code
     public static void main(String args[])
     {
 
         int a[] = { 1 , 1 , 2 , 3 , 4 , 2 , 1 };
         int len = 7 ;
         int max = Integer.MIN_VALUE;
         for ( int i = 0 ; i < len; i++) {
             // Getting the max element of the array
             if (a[i] > max) {
                 max = a[i];
             }
         }
         int freq[] = new int [max + 1 ];
 
         for ( int i = 0 ; i < max + 1 ; i++)
             freq[i] = 0 ;
 
         // Calculating frequency of each element
         for ( int i = 0 ; i < len; i++) {
             freq[a[i]]++;
         }
         // Function call
         NFG(a, len, freq);
     }
}
 
// This code is contributed by Arnab Kundu

Python3

'''NFG function to find the next greater frequency
    element for each element in the array'''
 
 
def NFG(a, n):
 
     if (n < = 0 ):
         print ( "List empty" )
         return []
 
     # stack data structure to store the position
     # of array element
     stack = [ 0 ] * n
 
     # freq is a dictionary which maintains the
     # frequency of each element
     freq = {}
     for i in a:
         freq[a[i]] = 0
     for i in a:
         freq[a[i]] + = 1
 
     # res to store the value of next greater
     # frequency element for each element
     res = [ 0 ] * n
 
     # initialize top of stack to -1
     top = - 1
 
     # push the first position of array in the stack
     top + = 1
     stack[top] = 0
 
     # now iterate for the rest of elements
     for i in range ( 1 , n):
 
         ''' If the frequency of the element which is
             pointed by the top of stack is greater
             than frequency of the current element
             then push the current position i in stack'''
         if (freq[a[stack[top]]] > freq[a[i]]):
             top + = 1
             stack[top] = i
 
         else :
             ''' If the frequency of the element which
             is pointed by the top of stack is less
             than frequency of the current element, then
             pop the stack and continuing popping until
             the above condition is true while the stack
             is not empty'''
 
             while (top > - 1 and freq[a[stack[top]]] < freq[a[i]]):
                 res[stack[top]] = a[i]
                 top - = 1
 
             # now push the current element
             top + = 1
             stack[top] = i
 
     '''After iterating over the loop, the remaining
     position of elements in stack do not have the
     next greater element, so print -1 for them'''
     while (top > - 1 ):
         res[stack[top]] = - 1
         top - = 1
 
     # return the res list containing next
     # greater frequency element
     return res
 
 
# Driver Code
print (NFG([ 1 , 1 , 2 , 3 , 4 , 2 , 1 ], 7 ))

C#

// C# program of Next Greater Frequency Element
using System;
using System.Collections;
 
class GFG {
 
     /*NFG function to find the
     next greater frequency
     element for each element
     in the array*/
     static void NFG( int [] a, int n, int [] freq)
     {
 
         // stack data structure to store
         // the position of array element
         Stack s = new Stack();
         s.Push(0);
 
         // res to store the value of next greater
         // frequency element for each element
         int [] res = new int [n];
         for ( int i = 0; i < n; i++)
             res[i] = 0;
 
         for ( int i = 1; i < n; i++) {
             /* If the frequency of the element which is
                 pointed by the top of stack is greater
                 than frequency of the current element
                 then Push the current position i in stack*/
 
             if (freq[a[( int )s.Peek()]] > freq[a[i]])
                 s.Push(i);
             else {
                 /*If the frequency of the element which
                 is pointed by the top of stack is less
                 than frequency of the current element, then
                 Pop the stack and continuing Popping until
                 the above condition is true while the stack
                 is not empty*/
 
                 while (freq[a[( int )( int )s.Peek()]]
                            < freq[a[i]]
                        && s.Count > 0) {
                     res[( int )s.Peek()] = a[i];
                     s.Pop();
                 }
 
                 // now Push the current element
                 s.Push(i);
             }
         }
 
         while (s.Count > 0) {
             res[( int )s.Peek()] = -1;
             s.Pop();
         }
 
         for ( int i = 0; i < n; i++) {
 
             // Print the res list containing next
             // greater frequency element
             Console.Write(res[i] + " " );
         }
     }
 
     // Driver code
     public static void Main(String[] args)
     {
 
         int [] a = { 1, 1, 2, 3, 4, 2, 1 };
         int len = 7;
         int max = int .MinValue;
         for ( int i = 0; i < len; i++) {
             // Getting the max element of the array
             if (a[i] > max) {
                 max = a[i];
             }
         }
         int [] freq = new int [max + 1];
 
         for ( int i = 0; i < max + 1; i++)
             freq[i] = 0;
 
         // Calculating frequency of each element
         for ( int i = 0; i < len; i++) {
             freq[a[i]]++;
         }
         NFG(a, len, freq);
     }
}
 
// This code is contributed by Arnab Kundu

输出如下：

[-1, -1, 1, 2, 2, 1, -1]

时间复杂度：O(n)。

木子山

发表评论

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