KJCP01 - Editorial

general
, , , , , , ,
1

PROBLEM LINK:

Sorting Tool

Practice
Contest

Author, Tester, Editorialist: Dipen Ved

Under KJSCE CODECELL

DIFFICULTY:

EASY

PREREQUISITES:

STL, Balanced Binary Search Tree

PROBLEM:

The problem input consists of N. numbers, smaller than or equal to M.
The output must be sorted so that for two numbers A and B, A will appear before B if the number of times A appears in the original order is larger than the number of times B does. If the number of occurrences is equal, the number whose value appears sooner in the input should appear sooner in the sorted sequence.

QUICK EXPLANATION:

Help Chaitya by creating a “frequency sorter”

EXPLANATION:

This problem actually asks you to sort given array of numbers on the basis of frequency and orders the number of same frequency on the basis of their entry in the array.
There are two methods to solve this problem
1.Balanced Binary Search Tree
2.C++ Standard Template Library

Vector is used of a num struct having value,count and index.

struct num {
        int val, count, index;
        num(int v, int c, int i) {
                val=v;
                count=c;
                index=i;
        }
};

vector <num> v;

A custom sorting function is implemented to sort the vector of num struct. This makes the sorting handy to use. The condition is added. If the number of occurrences is equal, the number whose value appears sooner in the input should appear sooner in the sorted sequence.

bool operator < (num a, num b) {
        if(a.count==b.count) {
                return a.index<b.index;
        }
        else return a.count>b.count; 
}

Then vector is sorted accordingly and finally its content is printed.

sort(v.begin(), v.end());

STL is used to solve this problem,however it can be solved using BBST also.

AUTHOR’S AND TESTER’S SOLUTIONS:

Solution can be found here.