h******e
发帖数: 52 | 1 you have an img data as an array, output the data for upsampling. For
example,
[1, 2, 3, 4, 5, 6] as width 3(2 rows) ==> upsample 2 times would be [1 1 2 2
3 3 1 1 2 2 3 3 4 4 5 5 6 6 4 4 5 5 6 6]
int[] UpSampling(int[] input, int width, int times)
{
//check the validation of input parameters
...
int numRows = input.Length / width;
int[] result = new int[input.Length * Math.Pow(times, 2)];
int index = 0;
for(int i = 0; i < numRows; i++)
{
for(int j = 0; j < times; j++)
{
for(int k = 0; k < width; k++)
{
for(int l = 0; l < times; l++)
{
result[index++] = input[i*width + k];
}
}
}
}
return result;
}
我这个算法用了4 个 loop, 看起来有点笨， 不过performance还是o(n). 和面试官讨
论，他没有反对，不过最后估计还是挂在了这个题上
大家有没有更好的办法？
| t*********r
发帖数: 387 | 2 Possible solution:
Output[i] = f(i, width, times)
Determine what f is, and then write a single loop over the output array. | L*******k
发帖数: 42 | 3 这题充其量warmup吧不用这么复杂，按行写output不就行了
【在 t*********r 的大作中提到】
: Possible solution:
: Output[i] = f(i, width, times)
: Determine what f is, and then write a single loop over the output array.
| e**y
发帖数: 784 | 4 估计也没有比O(n)更好的了吧
你自己背景是做imaging的？
2
【在 h******e 的大作中提到】
: you have an img data as an array, output the data for upsampling. For
: example,
: [1, 2, 3, 4, 5, 6] as width 3(2 rows) ==> upsample 2 times would be [1 1 2 2
: 3 3 1 1 2 2 3 3 4 4 5 5 6 6 4 4 5 5 6 6]
: int[] UpSampling(int[] input, int width, int times)
: {
: //check the validation of input parameters
: ...
:
: int numRows = input.Length / width;
| M******i
发帖数: 468 | 5 这个不是行和列上来都定好的了，那就可以pre-allocate 空间， 直接loop所有的数字
列就好了
the idea is
int cols = width * times;
int rows = input.size()/width + (input.size() % width == 0 ) ? 0 : 1;
vector> ret(rows, vector(cols, 0));
for (int i=0; i < rows; ++i) {
for (int j=0; j < cols; ++j) {
ret[i][j] = input[i*width+j/times];
}
}
// do some boundary handling here
少两个loop，清晰点：） | c****z
发帖数: 42 | 6 一个for loop就可以啦
def upsampling(arr, width, times):
new_width = width*times
new_height = len(arr)/width*times
ans = [None]*new_width*new_height
for i in xrange(len(ans)):
row, col = i/new_width/times, i%new_width/times
ori_index = row*width + col
ans[i] = arr[ori_index]
return ans |
|
