WeirdSort
SRM 321 · 2006-10-02 · by Mike Mirzayanov
SRM 321 · 2006-10-02 · by Mike Mirzayanov · Sorting
Problem Statement
Problem Statement
You are given a int[] data, and you must order the elements of data such that no two consecutive elements have consecutive values. In other words, result[i] + 1 != result[i + 1] for all i, where 0 <= i < n-1, and n is the number of elements in data. If more than one ordering exists, return the one that comes first lexicographically.
Constraints
- data will contain between 1 and 50 elements, inclusive.
- Each element of data will be between 0 and 1000, inclusive.
Examples
0)
{1, 2}
Returns: {2, 1 }
Only one possible ordering exists.
1)
{1, 2, 3}
Returns: {1, 3, 2 }
There are only three possible orderings: {1, 3, 2}, {2, 1, 3} and {3, 2, 1}. The first one is lexicographically smallest.
2)
{1, 1, 1, 1, 2, 2, 2, 2, 2}
Returns: {2, 2, 2, 2, 2, 1, 1, 1, 1 }
All 2's should be before 1's.
3)
{1, 2, 3, 4, 5, 6}
Returns: {1, 3, 2, 4, 6, 5 }
4)
{1, 1, 2, 2, 3, 3}
Returns: {1, 1, 3, 3, 2, 2 }
Submissions are judged against all 151 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class WeirdSort with a public method vector<int> sortArray(vector<int> data) · 151 test cases · 2 s / 256 MB per case