Walainlord
BAN USERPre-process can be done in O(n^2) time with O(n^2) space.
Query can be done in O(1) time.
Pre-process:
1. Initialize a n by n matrix A with 0;
2. For each rectangle (x y)(x' y'), A[y'][x'] = A[y - 1][x - 1] += 1; A[y - 1][x'] = A[y'][x-1] -= 1;
3. Starting from the upper right corner of the matrix(assuming the matrix is upside down, which coincide with the coordinate), A[i][j] += A[i + 1][j] + A[i][j + 1];
4. Now A contains the corresponding coverage at each location
Query:
for a pixel at (x, y), return A[y][x]
The answer is not correct because there could be pure circles in the array. For example, given an input like 1, 2, 2, 3. The algorithm will give 3 instead of 2.
- Walainlord December 12, 2012int duplicate(int A[], int n)
{
for(int i = 0; i < n; i++)
{
while(A[i] - i != 1)
{
if(A[i] == A[A[i] - 1])
return A[i];
else
swap(A[i], A[A[i] - 1]);
}
}
}
distance traveled: D/vb, where D is the initial distance and vb is the speed of the bird;
Time U turned: infinite. Suppose finite, at the last U turn, suppose the trains are d apart, in d/(vt + vb) time, the bird run into the other train, however the trains are still d(1 - 2vt/(vt + vb))>0 apart, which means there is another U turn. contradiction
This could be implemented using a hash table and a RB tree. In C++ STL, it would be a hash_map and map
- Walainlord December 28, 20121. lookup, just lookup the hash_map
2. range lookup: find the key1 in map, iterate the map to key2, and while iterating, output all the values from hash_map. O(n), where n is the # of keys between key 1 and 2.