How can I arrange the elements in an array based on the number of occurrences of that value in ascending order in java.
This is what I've tried:
int a[]={0,0,0,1,3,3,2,1,3,5,6,0};
int b=a.length;
for(int i=0;i<b;i++) {
for(int j=0;j<i;j++) {
int temp;
if( a[j]>a[i]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
for(int r=0;r<a.length;r++) {
System.out.println(a[r]);
}
Using TreeMap to store the element as key,count of occurrences as value and then sorting it based on values. Java 8 streams make below code concise and simple to understand
int[] a = {1,1,2,2,3,3,3,4,4,5,5,5,5,6,6,6,8};
// new element ? store its count as 1 , else increment its count
TreeMap<Integer,Integer> m1 = new TreeMap<>();
for(int i : a)
{
if(m1.containsKey(i))
{m1.put(i,m1.get(i)+1);}
else {m1.put(i,1);}
};
// sort and then if element i occurs n times, simply loop to add so in arraylist
ArrayList<Integer> b = new ArrayList<>();
m1.entrySet().stream()
.sorted((k1, k2) -> -k1.getValue().compareTo(k2.getValue())).forEach(e -> {
for(int i=0;i<e.getValue();i++)
b.add(e.getKey());
});
Arrays.stream(a).forEach(i -> System.out.print(i+ " "));
System.out.println();
b.stream().forEach(i -> System.out.print(i+ " "));
}
Sort the array elements based on its frequencies
Assumptions -
1. Sort the array based on its natural occurrence in an ascending order
2. If two numbers having same frequencies then sort them based on natural number precedence
Example: - [ 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5]
Output: - [ 5, 4, 4, 2, 2, 2, 3, 3, 3, 1, 1, 1, 1, 1]
Solution: -
1. Create a HashMap which stores the array elements and its occurrences
2. Put hashmap into a List where we can apply sorting based on its frequencies using a customized comparator
3. Object Comparision is Java: -
if Obj1 is less then Obj2 then return -1
if Obj1 is equal to Obj2 then return 0
if Obj1 is greater then Obj2 then return +1
4. In our case, if two numbers have the same frequences then we should put the number which has natural precedence in the output
Ex: - if above example, number 2 and 3 occurred 3 times hence 2 should come first
public static void sortTheArrayByFrequency(int[] array){
Map<Integer, Integer> map = new HashMap<>();
//put array elements based on its frequncies
for(int i : array){
map.put(i, map.getOrDefault(i,0)+1);
}
//Put the hashmap into a list where we use customized comparator
List<Map.Entry<Integer, Integer>> list = new ArrayList<>();
for(Map.Entry<Integer, Integer> e : map.entrySet()){
list.add(e);
}
// list looks like [1=5, 2=3, 3=3, 4=2, 5=1]
Collections.sort(list, (a, b) -> {
// if its ouccrances are same then sort natually
//else sort based on freqncies
if(a.getValue() == b.getValue())
return a.getKey() - b.getKey();
else
return a.getValue() - b.getValue();
});
// list looks like [5=1, 4=2, 2=3, 3=3, 1=5]
for(Map.Entry<Integer, Integer> e : list){
int num = e.getValue();
while(num!=0){
System.out.print(e.getKey()+ " ");
num--;
}
}
}
Output:-
5 4 4 2 2 2 3 3 3 1 1 1 1 1
public class SortBasedOnFrequency {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] arr = new String[] { "abc", "def", "qas", "abc", "abc", "def" };
new SortBasedOnFrequency().sort(arr);
}
void sort(String[] a) {
Map<String, Integer> map = new HashMap<>();
for (String s : a) {
//convert array to map putting key as the array element and value as the
//number of occurence.
map.put(s, map.get(s) == null ? 1 : map.get(s) + 1);
}
List<Map.Entry<String, Integer>> mapEntryList = new ArrayList<>map.entrySet());// sort mapEntry list based on value
Collections.sort(mapEntryList, new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
// TODO Auto-generated method stub
return o1.getValue().compareTo(o2.getValue());
}
});
//print the object in sorting order of the occurrence.
for (Entry<String, Integer> m : mapEntryList) {
System.out.println(m.getKey() + " " + m.getValue());
}
}
}
I didn't like the answers above, so I'm adding what I did. The general idea is pretty simple - just sort the list by Comparator that will take as an argument the hash map.
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] ar = new int[] {0,0,0,1,3,3,2,1,3,5,6,0};
Map<Integer,Integer> map = new HashMap<>();
List<Integer> output = new ArrayList<>();
for(int current : ar) {
int count = map.getOrDefault(current, 0);
map.put(current, count + 1);
output.add(current);
}
FrequencyComparator comp = new FrequencyComparator(map);
Collections.sort(output, comp);
for(Integer i : output){
System.out.print(i + " ");
}
}
}
And the FrequencyComparator:
import java.util.Comparator;
import java.util.Map;
public class FrequencyComparator implements Comparator<Integer> {
private final Map<Integer,Integer> freqMap;
FrequencyComparator(Map<Integer,Integer> i_freqMap) { this.freqMap = i_freqMap; }
@Override
public int compare(Integer k1, Integer k2) {
int freqCompare = freqMap.get(k1).compareTo(freqMap.get(k2));
int valueCompare = k1.compareTo(k2);
// If frequency is equal, then just compare by value, otherwise - compare by the frequency.
if(freqCompare == 0)
return valueCompare;
else
return freqCompare;
}
}
output:
2 5 6 1 1 3 3 3 0 0 0 0
Simply Using Arrays.
import java.util.*;
public class SortAccordingToFrequency {
public static void main(String[] args) {
int r;
int b[]={1,1,1,2,1,2,3,6,6,5};int i;int n=b.length;int k=0;
Arrays.sort(b);
int[] a=new int[n+1];
for(r=0;r<n;r++){
a[r]=b[r];}
a[r]=1882737378; //Any arbitrary value.
int c=1;int in[]=new int[10];
int[] e=new int[10];
for(i=0;i<n;i++){
if(a[i]==a[i+1])
c++;
else{
e[k]=a[i];
in[k]=c;k++;
c=1;
}
}
for (int f = 0; f < k; f++) {
for (int g = 0; g < k-f-1; g++) {
if (in[g] > in[g+1]){
int[] ans = swap(in[g], in[g+1]);
in[g]=ans[0];
in[g+1]=ans[1];
int[] an = swap(e[g], e[g+1]);
e[g]=an[0];
e[g+1]=an[1];
}
}
}
int d=0;
for(int x=0;x<k;x++){
for(int y=0;y<in[x];y++){
System.out.print(e[d]);
}d++;
}
}
static int[] swap(int n1,int n2)
{
int temp;
temp=n1;
n1=n2;
n2=temp;
int ans[]=new int[2];
ans[0]=n1;
ans[1]=n2;
return ans;
}
}
public class Frequency {
static int key;
public static void main(String[] args) {
Integer[] nums = { 7, 3, 4, 3, 4, 3, 4, 3, 6, 5, 7 };
Map<Integer, Integer> m1;
//Convert the integer array into an Array List.
ArrayList<Integer> numbers = new ArrayList<Integer>(Arrays.asList(nums));
//ArrayList to store the number of occurences of numbers.
List<Integer> values = new ArrayList<Integer>();
//ArrayList to show the array in requested order.
List<Integer> output = new ArrayList<Integer>();
m1 = new LinkedHashMap<Integer, Integer>();
for (int a : numbers) {
//Add data in Hash map where key is number and value is the total occurences of that number.
if (m1.containsKey(a)) {
int value = m1.get(a);
m1.put(a, ++value);
} else {
m1.put(a, 1);
}
}
System.out.println(m1);
for (Map.Entry<Integer, Integer> entry : m1.entrySet()) {
values.add(entry.getValue());
}
Collections.sort(values, Collections.reverseOrder());
System.out.println(values.toString());
for (int m = 0; m < values.size(); m++) {
for (Map.Entry<Integer, Integer> entry : m1.entrySet()) {
if (entry.getValue().equals(values.get(m))) {
key = entry.getKey();
System.out.println("Key is" + key);
for (int k = values.get(m); k > 0; k--) {
output.add(key);
}
break;
}
}
m1.remove(key);
}
System.out.println(output.toString());
}
}
I am a newbie to coding, I tried this by using "for loop". Here is my code -
//Driver Program
public static void main(String args[])
{
int[] array = { 2, 2, 3, 4, 5, 12, 2, 3, 3, 3, 12 };
sortByCount(array);
}
//Array element's count
static int elementsCount(int ar[], int n)
{
int count = 0;
for(int i : ar)
{
int max = n;
if(i == max)
{
count++;
}
max = i;
}
return count;
}
//Ascending order sort by count
static void sortByCount(int ar[])
{
int temp = 0;
for(int i = 0; i < ar.length; i++)
{
for(int j = i + 1; j < ar.length; j++)
{
if(elementsCount(ar, ar[i]) > elementsCount(ar, ar[j]))
{
temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;
}
}
}
printArray(ar);
}
//Print Array
static void printArray(int[] ar)
{
for(int i : ar)
{
System.out.println(i);
}
}
Using Map,ArrayList and Comparator
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Map.Entry;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
public class OrderArrayFrequency {
public static void main(String[] args) {
int nums[] = {0,0,0,1,3,3,2,1,3,5,6,0};
ConcurrentHashMap<Integer, Integer> counts = new ConcurrentHashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (counts.containsKey(nums[i])) {
Integer c = counts.get(nums[i]) + 1;
counts.put(nums[i], c);
} else {
counts.put(nums[i], 1);
}
}
ArrayList<Integer> list = new ArrayList<>();
for (Integer i : counts.keySet()) {
list.add(counts.get(i));
}
Collections.sort(list, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if (o1 < o2)
return -1;
return 0;
}
});
Set<Entry<Integer, Integer>> set = counts.entrySet();
for (Integer i : list) {
for (Entry<Integer, Integer> entry : set) {
if (entry.getValue().equals(i)) {
System.out.print(entry.getKey()+":"+entry.getValue()+ " ");
counts.remove(entry.getKey());
}
}
}
}
}
Output : 2:1 5:1 6:1 1:2 3:3 0:4
import java.util.*;
class SortArrayByFrequency
{
public static void main(String[] args)
{
int a[]={2,2,2,2,4,4,4,4,4,4,5,6,6,6,6,6,1,1,1};
int count=0;
int k[]=new int[10];// for elements
int v[]=new int[10];//store the frquency of corresponding element
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<a.length;i++)
{
if(map.containsKey(a[i]))
{
map.put(a[i],map.get(a[i])+1);
}
else
{
map.put(a[i],1);
}
}
Set<Integer> keys=map.keySet();
int i=0,j=0;
for(int key:keys){
//System.out.println(key+" : "+map.get(key));
v[i++]=map.get(key);
k[j++]=key;
}
System.out.println("--------------------");
//Sort the array which contains the frquency of elements
for(int f=0;f<i-1;f++){
//System.out.println(k[f]+" "+v[f]);
int min=f;
for(int g=f+1;g<i;g++)
{
if(v[min]>v[g])
{
min=g;
}
}
int temp=v[min];
v[min]=v[f];
v[f]=temp;
//here we swap the element according to sorting ------------
int temp1=k[min];
k[min]=k[f];
k[f]=temp1;
}
System.out.println("-----Array sort by frequency in ascending order------------");
for(int l=0;l<i;l++){
//System.out.println(v[l]+" :: "+k[l]);
for(int p=0;p<v[l];p++)
System.out.print(k[l]+" ");
}
}
}
Ascending order
//OUTPUT: 5 1 1 1 2 2 2 2 6 6 6 6 6 4 4 4 4 4 4
Already it has been answered but there's no good explanation of the code.So I will try that here.
Let the array to be sorted be : int[] array = {4,4,2,2,2,2,3,3,1,1,6,7,5}
First of all let us count the frequency of each number:
To do so we will create a HashMap data-structure which will have the array elements as Key and their frequency as value.And to store our output we will have a output list.
HashMap<Integer,Integer> freqMap = new HashMap<>();
ArrayList<Integer> output = new ArrayList<>();
getOrDefault(key,defaultValue) : This is a convenient way to handle the scenario where we want a returned value other than null which is being returned by get method whenever the key was not found.
Coming to the code:
for(int current : array)
{
int count = freqMap.getOrDefault(current,0); // if arrayelement is encountered first time it returns 0 otherwise it returns the actual count
freqMap.put(current,count++); // we increase the count by one and put it in the map
output.add(current); // we also add the element in the list.
}
Now we have out elements mapped with their frequency in HashMap.
- 2 comes four times
- 3 comes two times
- 4 comes two times
- 5,6 and 7 comes one time.
Now we need to sort the output list according to the frequency. For that we implement the comparator interface. In this interface we have a method
public int compare(Object obj1, Object obj2) //It compares the first object with the second object.
So we create a class SortComparator to implement this interface and create an object comp of class SortComparator.
SortComparator comp = new SortComparator(freqMap);
Collections.sort(output,comp);
for(Integer i : output)
{
System.out.print(i + " ");
}
This is the implementation of the Comparator interface:
class SortComparator implements Comparator<Integer>
{
private final Map<Integer,Integer> freqMap;
SortComparator(Map<Integer,Integer>freqMap)
{
this.freqMap = freqMap;
}
public int compare(Integer k1,Integer k2)
{
//Comparing by frequency
int freqCompare = freqMap.get(k2).compareTo(freqMap.get(k1));
//Comparing by value
int valueCompare = k2.compareTo(k1);
if(freqCompare == 0)//frequency of both k1 and k2 is same then
{
return valueCompare;
}
else
{
return freqCompare;
}
}
// sorting of an array in decreasing order on the basis of their frequencies.
import java.util.*;
class sorting {
static int x = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for(int i=0; i<n; i++){
a[i] = sc.nextInt();
}
Arrays.sort(a);
// l is number of distinct elements in array a.
int l=1;
for(int i=0; i<n-1; i++){
if(a[i]!=a[i+1]){
l++;
}
}
// creating a 2d array from a 1d array having elements and their frequencies.
int b[][] = new int[l][2];
b[x][0] = a[0];
int c=1;
for(int i=1; i<n; i++){
if(a[i]!=a[i-1]){
b[x][1]=c;
x++;
c=1;
b[x][0] = a[i];
}
else{
c++;
}
if(i==n-1){
b[x][1]=c;
}
}
// sorting 2d array according their frequencies.
for(int i=0; i<b.length; i++){
for(int j=i; j<b.length; j++){
if(b[i][1]<b[j][1]){
int t = b[i][1];
b[i][1] = b[j][1];
b[j][1] = t;
t = b[i][0];
b[i][0] = b[j][0];
b[j][0] = t;
}
}
}
for(int i=0; i<b.length; i++){
int k=b[i][1];
for(int j=0; j<k; j++){
System.out.print(b[i][0]+" ");
}
}
}
// bubble sort.
public static void sort(int a[]) {
int n = a.length;
for(int i=0; i<n; i++){
for(int j=i; j<n; j++){
if(a[i]>a[j]){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
}
}
Since Java 8 you can achieve this with a one-liner (split into several lines for better readability ;-)
int[] numbers = {0, 0, 0, 1, 3, 3, 2, 1, 3, 5, 6, 0};
List<Integer> result = IntStream.of(numbers)
.boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
.entrySet()
.stream()
.sorted(Comparator.comparing(Map.Entry::getValue))
.map(e -> Stream.generate(e::getKey).limit(e.getValue()))
.flatMap(Function.identity())
.collect(Collectors.toList());
or, if you prefer an array as a result
int[] result = IntStream.of(numbers)
.boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
.entrySet()
.stream()
.sorted(Comparator.comparing(Map.Entry::getValue))
.map(e -> Stream.generate(e::getKey).limit(e.getValue()))
.flatMap(Function.identity())
.mapToInt(Integer::intValue)
.toArray();
Answer in python:
n=input()
arr=[int(i) for i in n.split(' ')]
dict={}
for i in arr:
if(i in dict.keys()):
dict[i]+=1
else:
dict[i]=1
ans=[]
while len(ans)<=len(arr) and dict!={}:
maxval=min(list(dict.values()))
keys=[]
for key in dict.keys():
if(dict[key]==maxval):
keys+=[key]
keys=sorted(keys)
for i in keys:
ans+=[i]*dict[i]
del dict[i]
print(ans)
import java.util.Arrays;
import java.util.Comparator;
public class TestString {
public static void main(String[] args) {
int arrTemp[] = { 2, 2, 2, 1, 1, 4, 5, 6, 6, 7, 7, 7, 7 };
Arrays.sort(arrTemp);
Integer[][] sortedArray = new Integer[6][2];
int count = 0;
sortedArray[count][0] = arrTemp[0];
sortedArray[count][1] = 1;
for (int i = 0; i < arrTemp.length - 1; i++) {
for (int j = 1; j < arrTemp.length; j++) {
if (arrTemp[i] == arrTemp[j]) {
sortedArray[count][1] = sortedArray[count][1] + 1;
i = j;
} else {
++count;
sortedArray[count][0] = arrTemp[j];
sortedArray[count][1] = 1;
i = j;
}
}
}
Arrays.sort(sortedArray, new Comparator<Integer[]>() {
@Override
public int compare(Integer[] o1, Integer[] o2) {
return o1[1].compareTo(o2[1]);
}
});
for (int row = 0; row < 6; row++) {
for (int col = 0; col < sortedArray[row][1]; col++) {
System.out.print(sortedArray[row][0] + " ");
}
}
}
}
Sort array based on frequency:
public static void main(String[] args) {
int arr[] = { 2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8 };
Map<Integer, Integer> mp = new LinkedHashMap<>();
List<Integer> res = new ArrayList<>();
int count = 1;
for (int i = 0; i < arr.length; i++) {
if (!mp.containsKey(arr[i])) {
mp.put(arr[i], count);
} else {
mp.put(arr[i], mp.get(arr[i]) + 1);
}
}
if (!mp.containsValue(2)) {
for (Integer ab : arr)
res.add(ab);
Collections.sort(res);
Collections.reverse(res);
System.out.println(res);
} else {
Set<Entry<Integer, Integer>> set = mp.entrySet();
List<Entry<Integer, Integer>> list = new ArrayList<>(set);
Collections.sort(list, new Comparator<Entry<Integer, Integer>>() {
@Override
public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2) {
if (obj2.getValue() > obj1.getValue())
return 1;
if (obj2.getValue() < obj1.getValue())
return -1;
else
return 0;
}
});
for (Map.Entry<Integer, Integer> e : list) {
for (int i = 1; i <= e.getValue(); i++)
res.add(e.getKey());
}
System.out.println(res);
}
}