hoolala
BAN USERO(n^2)
1. sort persons by height and num greater before
2. find place for each person (from short to high)
class Person{
public int Height;
public int Greater;
public static bool operator > (Person p1, Person p2){
return p1.Height > p2.Height || p1.Height == p2.Height && p1.Greater > p2.Greater;
}
public static bool operator < (Person p1, Person p2){
return p1.Height < p2.Height || p1.Height == p2.Height && p1.Greater < p2.Greater;
}
public static bool operator == (Person p1, Person p2){
return p1.Height == p2.Height && p1.Greater == p2.Greater;
}
}
int[] HeightSort(int[] heights, int[] greaters){
if(heights == null || greaters == null || heights.Length != greaters.Length){
return null;
}
int len = heights.Length;
Person[] ps = new Person[len];
for(int i = 0; i < len; ++i){
ps[i] = new Person{Height = heights[i], Greater = greaters[i]};
}
QuickSort(ps);
int[] ret = new int[len];
for(int i = 0; i < len; ++i){ret[i] = -1;}
for(int i = 0; i < len; ++i){
int j = 0;
for(int idx = 0; idx < len; ++idx){
if(j == ps[i].Greater){
break;
}
if(ret[idx] == -1){
++j;
}
}
if(idx == len){
return null;
}
ret[idx] = ps[i].Height;
}
return ret;
}
public bool isMatch(char* text, char* pattern){
if(text == NULL && pattern == NULL){
return true;
}
if(pattern == NULL){
return false;
}
if(text == NULL && *(pattern + 1) != '*'){
return false;
}
if(*(pattern + 1) == '*'){
return isMatch(text, pattern + 2)
|| (*text == *pattern || *pattern == '.') && isMatch(text + 1, pattern);
}
return (*text == *pattern || *pattern == '.') && isMatch(text + 1, pattern + 1);
}
O(n^2)
1. sort persons by height and num greater before
2. find place for each person (from short to high)
- hoolala December 06, 2013