如果两个数字的频率相同，则以递减的频率打印数组中的元素，然后打印第一个数字。
null
例如：
Input: arr[] = {2, 5, 2, 8, 5, 6, 8, 8}Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}Input: arr[] = {2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8}Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6, -1, 9999999}
方法1（使用排序）
- 使用排序算法对元素进行排序 O（nlogn）
- 扫描排序后的数组，并构建一个二维数组，其中包含元素和计数 O（n）。
- 根据计数对2D数组进行排序 O（nlogn） .
例子：
Input 2 5 2 8 5 6 8 8 After sorting we get 2 2 5 5 6 8 8 8 Now construct the 2D array as 2, 2 5, 2 6, 1 8, 3 Sort by count 8, 3 2, 2 5, 2 6, 1
如果频率相同，如何保持元素的顺序？
如果频率相同，上述方法无法确定元素的顺序。为了处理这个问题，我们应该在步骤3中使用索引，如果两个计数相同，那么我们应该首先处理（或打印）具有较低索引的元素。在步骤1中，我们应该存储索引而不是元素。
Input 2 5 2 8 5 6 8 8 After sorting we get Element 2 2 5 5 6 8 8 8 Index 0 2 1 4 5 3 6 7 Now construct the 2D array as Index, Count 0, 2 1, 2 5, 1 3, 3 Sort by count (consider indexes in case of tie) 3, 3 0, 2 1, 2 5, 1 Print the elements using indexes in the above 2D array.
以下是上述方法的实施情况——
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; } |
输出 :
8 8 8 2 2 5 5 6 -1 9999999
感谢Gaurav Ahirwar提供上述实施。
方法2（使用哈希和排序） 使用散列机制，我们可以将元素（也是第一个索引）及其计数存储在散列中。最后，根据哈希元素的计数对其进行排序。 以下是上述方法的实施情况-
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); } } |
蟒蛇3
# 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) |
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> |
输出 :
8 8 8 2 2 5 5 6 -1 9999999
这也可以通过使用两个映射来解决，一个用于数组元素作为索引，第二个映射之后的键是频率，值是数组元素。
方法3（使用BST和排序）
- 在BST中逐个插入元素，如果元素已经存在，则增加节点的计数。二叉搜索树的节点（在这种方法中使用）如下所示。
C
struct tree { int element; int first_index /*To handle ties in counts*/ int count; } BST;</ div > |
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 |
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 |
- 将第一个索引和相应的BST计数存储在2D数组中。
- 根据计数对2D数组进行排序（如果是并列的，则使用索引）。
时间复杂性： O（nlogn）如果 自平衡二叉搜索树 被使用了。这是在中国实施的 第二组 . https://youtu.be/NBXf9vCksuM 第二组： 按频率排序元素|集2 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
