guzhiwei
BAN USER1. Record the positions for each character, ex,
For "abcbdef", record as
a->0
b->1,3
c->2
d->4
e->5
f->6
2. Get the most tight range for the search characters {'b','e'}, that is to get the tight range of
b->1,3
e->5
Use back-tracing, we can get the final result. While coding, could use some rules for pruning.
The complexity might be O(N) <not sure>.
This problem is not clear: how to seperate the group?
There must be a number x, the left group < x, and the right group >= x.
If x is given, the solution is:
1. Identify how many elements >= x, and get the first_large position;
2. Iteratively by each element, get the final position, and store to a position array;
3. Swap the elements according to the position array;
The complexity is O(N) in both time and space.
The important part is the comparison function, in this problem, we need to ensure:
1. odd number is always larger than even number;
2. even number is in the reverse order;
so we can define the comparison function as
int compare(int a, int b)
{
if(is_odd(a) && is_odd(b)) return a - b;
if(is_odd(a) && is_even(b)) return 1;
if(is_even(a) && is_odd(b)) return -1;
if(is_even(a) && is_even(b)) return b - a;
throw exception("unreachable");
}
this is a little time consuming, we can think of a better way, let us think.... :D
This is to merge two arrays, the problem is to merge K arrays. :D
- guzhiwei August 20, 2010