Ordenar elementos por frecuencia | Serie 1

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *