Imprime los elementos de una array en frecuencia decreciente si 2 números tienen la misma frecuencia y luego imprime el que vino primero.
Ejemplos:
CPP
// Sort elements by frequency. If two elements have same
// count, then put the elements that appears first
#include <bits/stdc++.h>
using namespace std;
// Used for sorting
struct ele {
int count, index, val;
};
// Used for sorting by value
bool mycomp(struct ele a, struct ele b)
{
return (a.val < b.val);
}
// Used for sorting by frequency. And if frequency is same,
// then by appearance
bool mycomp2(struct ele a, struct ele b)
{
if (a.count != b.count)
return (a.count < b.count);
else
return a.index > b.index;
}
void sortByFrequency(int arr[], int n)
{
struct ele element[n];
for (int i = 0; i < n; i++) {
// Fill Indexes
element[i].index = i;
// Initialize counts as 0
element[i].count = 0;
// Fill values in structure
// elements
element[i].val = arr[i];
}
/* Sort the structure elements according to value,
we used stable sort so relative order is maintained.
*/
stable_sort(element, element + n, mycomp);
/* initialize count of first element as 1 */
element[0].count = 1;
/* Count occurrences of remaining elements */
for (int i = 1; i < n; i++) {
if (element[i].val == element[i - 1].val) {
element[i].count += element[i - 1].count + 1;
/* Set count of previous element as -1, we are
doing this because we'll again sort on the
basis of counts (if counts are equal than on
the basis of index)*/
element[i - 1].count = -1;
/* Retain the first index (Remember first index
is always present in the first duplicate we
used stable sort. */
element[i].index = element[i - 1].index;
}
/* Else If previous element is not equal to current
so set the count to 1 */
else
element[i].count = 1;
}
/* Now we have counts and first index for each element
so now sort on the basis of count and in case of tie
use index to sort.*/
stable_sort(element, element + n, mycomp2);
for (int i = n - 1, index = 0; i >= 0; i--)
if (element[i].count != -1)
for (int j = 0; j < element[i].count; j++)
arr[index++] = element[i].val;
}
// Driver program
int main()
{
int arr[] = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
sortByFrequency(arr, n);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Python3
# Python3 program that performs the following # operations: Sort elements by frequency. If two elements # have same count, then put the elements that appears first # Used for sorting class ele: def __init__(self): self.count = 0 self.index = 0 self.val = 0 def mycomp(a): return a.val # Used for sorting by frequency. And if frequency is same, # then by appearance def mycomp2(a): # using negative value for a.index # since the sorting should be in # descending order return (a.count, -a.index) def sortByFrequency(arr, n): element = [None for _ in range(n)] for i in range(n): element[i] = ele() # Fill Indexes element[i].index = i # Initialize counts as 0 element[i].count = 0 # Fill values in structure # elements element[i].val = arr[i] # Sort the structure elements according to value, # we used stable sort so relative order is maintained. # element.sort(key=mycomp) # initialize count of first element as 1 element[0].count = 1 # Count occurrences of remaining elements for i in range(1, n): if (element[i].val == element[i - 1].val): element[i].count += element[i - 1].count + 1 # Set count of previous element as -1, we are # doing this because we'll again sort on the # basis of counts (if counts are equal than on # the basis of index)*/ element[i - 1].count = -1 # Retain the first index (Remember first index # is always present in the first duplicate we # used stable sort. */ element[i].index = element[i - 1].index # Else If previous element is not equal to current # so set the count to 1 else: element[i].count = 1 # Now we have counts and first index for each element # so now sort on the basis of count and in case of tie # use index to sort.*/ element.sort(key=mycomp2) index = 0 for i in range(n - 1, -1, -1): if (element[i].count != -1): for j in range(element[i].count): arr[index] = element[i].val index += 1 # Driver program arr = [2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8] n = len(arr) sortByFrequency(arr, n) print(*arr) # This code is contributed by phasing17
C#
// Sort elements by frequency. If two elements have same
// count, then put the elements that appears first
using System;
using System.Collections.Generic;
// Used for sorting
class ele {
public int count, index, val;
};
// Used for sorting by value
class mycomp : Comparer<ele> {
public override int Compare(ele a, ele b)
{
return (a.val.CompareTo(b.val));
}
};
// Used for sorting by frequency. And if frequency is same,
// then by appearance
class mycomp2 : Comparer<ele> {
public override int Compare(ele a, ele b)
{
if (a.count != b.count)
return (a.count).CompareTo(b.count);
return (b.index).CompareTo(a.index);
}
};
class GFG {
static void sortByFrequency(int[] arr, int n)
{
ele[] element = new ele[n];
for (int i = 0; i < n; i++) {
element[i] = new ele();
// Fill Indexes
element[i].index = i;
// Initialize counts as 0
element[i].count = 0;
// Fill values in structure
// elements
element[i].val = arr[i];
}
/* Sort the structure elements according to value,
we used stable sort so relative order is
maintained.
*/
Array.Sort(element, new mycomp());
/* initialize count of first element as 1 */
element[0].count = 1;
/* Count occurrences of remaining elements */
for (int i = 1; i < n; i++) {
if (element[i].val == element[i - 1].val) {
element[i].count
+= element[i - 1].count + 1;
/* Set count of previous element as -1, we
are doing this because we'll again sort
on the basis of counts (if counts are
equal than on the basis of index)*/
element[i - 1].count = -1;
/* Retain the first index (Remember first
index is always present in the first
duplicate we used stable sort. */
element[i].index = element[i - 1].index;
}
/* Else If previous element is not equal to
current so set the count to 1 */
else
element[i].count = 1;
}
/* Now we have counts and first index for each
element so now sort on the basis of count and in
case of tie use index to sort.*/
Array.Sort(element, new mycomp2());
for (int i = n - 1, index = 0; i >= 0; i--)
if (element[i].count != -1)
for (int j = 0; j < element[i].count; j++)
arr[index++] = element[i].val;
}
// Driver program
public static void Main(string[] args)
{
int[] arr = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 };
int n = arr.Length;
sortByFrequency(arr, n);
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by phasing17
Javascript
// JavaScript program that performs the following
// operations: Sort elements by frequency. If two elements
// have same count, then put the elements that appears first
// Used for sorting
class ele {
constructor()
{
this.count;
this.index;
this.val;
}
};
// Used for sorting by value
function mycomp(a, b) { return (a.val > b.val); }
// Used for sorting by frequency. And if frequency is same,
// then by appearance
function mycomp2(a, b)
{
if (a.count != b.count)
return (a.count > b.count);
else
return a.index < b.index;
}
function sortByFrequency(arr, n)
{
let element = new Array(n);
for (var i = 0; i < n; i++) {
element[i] = new ele();
// Fill Indexes
element[i].index = i;
// Initialize counts as 0
element[i].count = 0;
// Fill values in structure
// elements
element[i].val = arr[i];
}
/* Sort the structure elements according to value,
we used stable sort so relative order is maintained.
*/
element.sort(mycomp);
/* initialize count of first element as 1 */
element[0].count = 1;
/* Count occurrences of remaining elements */
for (var i = 1; i < n; i++) {
if (element[i].val == element[i - 1].val) {
element[i].count += element[i - 1].count + 1;
/* Set count of previous element as -1, we are
doing this because we'll again sort on the
basis of counts (if counts are equal than on
the basis of index)*/
element[i - 1].count = -1;
/* Retain the first index (Remember first index
is always present in the first duplicate we
used stable sort. */
element[i].index = element[i - 1].index;
}
/* Else If previous element is not equal to current
so set the count to 1 */
else
element[i].count = 1;
}
/* Now we have counts and first index for each element
so now sort on the basis of count and in case of tie
use index to sort.*/
element.sort(mycomp2);
for (var i = n - 1, index = 0; i >= 0; i--)
if (element[i].count != -1)
for (var j = 0; j < element[i].count; j++)
arr[index++] = element[i].val;
}
// Driver program
let arr = [ 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 ];
let n = arr.length;
sortByFrequency(arr, n);
for (var i = 0; i < n; i++)
process.stdout.write(arr[i] + " ");
// This code is contributed by phasing17
CPP
// CPP program for above approach
#include <bits/stdc++.h>
using namespace std;
// Compare function
bool fcompare(pair<int, pair<int, int> > p,
pair<int, pair<int, int> > p1)
{
if (p.second.second != p1.second.second)
return (p.second.second > p1.second.second);
else
return (p.second.first < p1.second.first);
}
void sortByFrequency(int arr[], int n)
{
unordered_map<int, pair<int, int> > hash; // hash map
for (int i = 0; i < n; i++) {
if (hash.find(arr[i]) != hash.end())
hash[arr[i]].second++;
else
hash[arr[i]] = make_pair(i, 1);
} // store the count of all the elements in the hashmap
// Iterator to Traverse the Hashmap
auto it = hash.begin();
// Vector to store the Final Sortted order
vector<pair<int, pair<int, int> > > b;
for (it; it != hash.end(); ++it)
b.push_back(make_pair(it->first, it->second));
sort(b.begin(), b.end(), fcompare);
// Printing the Sorted sequence
for (int i = 0; i < b.size(); i++) {
int count = b[i].second.second;
while (count--)
cout << b[i].first << " ";
}
}
// Driver Function
int main()
{
int arr[] = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
sortByFrequency(arr, n);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
class GFG {
static Integer[] arr = { 2, 5, 2, 8, 5, 6, 8, 8 };
// Driver Code
public static void main(String[] args)
{
List<Integer> list = Arrays.asList(arr);
sortBasedOnFrequencyAndValue(list);
}
// Compare Function
public static void
sortBasedOnFrequencyAndValue(List<Integer> list)
{
int n = arr.length;
final HashMap<Integer, Integer> mapCount
= new HashMap<Integer, Integer>();
final HashMap<Integer, Integer> mapIndex
= new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
if (mapCount.containsKey(arr[i])) {
mapCount.put(arr[i],
mapCount.get(arr[i]) + 1);
}
else {
mapCount.put(arr[i],1); // Map to capture Count of elements
mapIndex.put(arr[i],i); // Map to capture 1st occurrence of elements
}
}
Collections.sort(list, new Comparator<Integer>() {
public int compare(Integer n1, Integer n2)
{
int freq1 = mapCount.get(n1);
int freq2 = mapCount.get(n2);
if (freq1 != freq2) {
return freq2 - freq1;
}
else {
return mapIndex.get(n1)
- mapIndex.get(
n2); // Elements with Lesser
// Index gets Higher
// Priority
}
}
});
System.out.println(list);
}
}
Python3
# Python program for above approach from collections import defaultdict # Sort by Frequency def sortByFreq(arr, n): # arr -> Array to be sorted # n -> Length of Array # d is a hashmap(referred as dictionary in python) d = defaultdict(lambda: 0) for i in range(n): d[arr[i]] += 1 # Sorting the array 'arr' where key # is the function based on which # the array is sorted # While sorting we want to give # first priority to Frequency # Then to value of item arr.sort(key=lambda x: (-d[x], x)) return (arr) # Driver Function if __name__ == "__main__": arr = [2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8] n = len(arr) solution = sortByFreq(arr, n) print(*solution)
C#
// C# program to implement the approach
using System;
using System.Collections.Generic;
public class GFG {
static int[] arr;
// Compare Function
public static void
sortBasedOnFrequencyAndValue(List<int> list)
{
int n = arr.Length;
Dictionary<int, int> mapCount
= new Dictionary<int, int>();
Dictionary<int, int> mapIndex
= new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
if (mapCount.ContainsKey(arr[i])) {
mapCount[arr[i]]++;
}
else {
mapCount[arr[i]]
= 1; // Map to capture Count of elements
mapIndex[arr[i]]
= i; // Map to capture 1st occurrence of
// elements
}
}
list.Sort(
(int n1, int n2) =>
mapCount[n1] != mapCount[n2]
? mapCount[n2].CompareTo(mapCount[n1])
: mapIndex[n1].CompareTo(mapIndex[n2])
// Elements with Lesser
// Index gets Higher
// Priority
);
foreach(var i in list) Console.Write(i + " ");
}
// Driver Code
public static void Main(string[] args)
{
arr = new int[] { 2, 5, 2, 6, -1,
9999999, 5, 8, 8, 8 };
List<int> list = new List<int>(arr);
sortBasedOnFrequencyAndValue(list);
}
}
// This code is contributed by phasing17
Javascript
<script>
let arr=[2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8];
// Compare Function
function sortBasedOnFrequencyAndValue(list)
{
let n = arr.length;
let mapCount
= new Map();
let mapIndex
= new Map();
for (let i = 0; i < n; i++) {
if (mapCount.has(arr[i])) {
mapCount.set(arr[i],
mapCount.get(arr[i]) + 1);
}
else {
mapCount.set(arr[i],1); // Map to capture Count of elements
mapIndex.set(arr[i],i); // Map to capture 1st occurrence of elements
}
}
list.sort(function(n1,n2){
let freq1 = mapCount.get(n1);
let freq2 = mapCount.get(n2);
if (freq1 != freq2) {
return freq2 - freq1;
}
else {
return mapIndex.get(n1)
- mapIndex.get(
n2); // Elements with Lesser
// Index gets Higher
// Priority
}
});
document.write(list.join(" "));
}
// Driver Code
sortBasedOnFrequencyAndValue(arr);
// This code is contributed by patel2127
</script>
C
struct tree {
int element;
int first_index /*To handle ties in counts*/
int count;
} BST;
Java
static class tree {
int element;
int first_index; /*To handle ties in counts*/
int count;
}
tree BST = new tree();
// This code is contributed by gauravrajput1
Python3
# Python code to implement the approach class Tree: element = None # to handle ties first_index = None count = None BST = Tree() # This code is contributed by phasing17
C#
public class tree {
public int element;
public int first_index; /* To handle ties in counts */
public int count;
}
tree BST = new tree();
// This code is contributed by gauravrajput1
Javascript
// JS code to implement the approach
class tree {
constructor()
{
this.element;
this.first_index; //To handle ties in counts
this.count;
}
};
// This code is contributed by phasing17
C++
#include <bits/stdc++.h>
using namespace std;
#define ppi pair<int,int>
/*IMPORTANT: comparator works in prority_queue only if they are a class which has
operator() overloaded in it (got this from stackoverflow) */
class Compare {
public:
bool operator()(pair<int, int> a, pair<int, int> b)
{
//b is at top and a is at bottom - have that in mind
if(a.first == b.first) //when freq same
return a.second > b.second; //smaller val stays at top
return a.first < b.first; // higher freq stays at top
}
};
void solve(vector<int> &arr){
int N = arr.size();
unordered_map<int ,int> mpp; // val, freq
for(int a : arr){
mpp[a]++;
}
//max heap - as max wise freq elements is what needed
priority_queue<ppi,vector<ppi>, Compare> maxH;
for( auto m : mpp){
maxH.push({m.second, m.first}); // freq, val
}
//now the max freq is at TOP of MAX heap
int i=0; // to maintain index to copy
while(maxH.size()>0){
int val = maxH.top().second; //val
int freq = maxH.top().first; //freq
while(freq-- ){
//freq - those many times make a copy
arr[i] = val;
i++;
}
maxH.pop(); // heapify happens and next top freq ele goes up
}
}
int main()
{
vector<int> vec{ 2, 5, 2, 8, 5, 6, 8, 8 };
int n = vec.size();
solve(vec);
for (int i = 0; i < n; i++)
cout << vec[i] << " ";
cout<<"\n";
return 0;
}
//Code done by Balakrishnan R (rbkraj000)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA