问个google面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个google面试题

问个google面试题# JobHunting - 待字闺中

B*12011-08-31 07:08

1 楼

Suppose we can compare two arrays like:
{4,2,3} > {3,5,6}
{4,2,3} < {4,3,0}
In each move, you can only switch a number with one of its neighbor. Given
an array and a number n, design an algorithm to make this array maximum
using n moves. (needs clarification)

f*t2011-08-31 07:08

2 楼

想了一下greedy不对

s*x2011-08-31 07:08

3 楼

say array A[0..(k-1)] contains k numbers
while (n)
{
x = min(n, k-1)
find i: 0<=i<=x such that A[i] is max among A[0..x]
for (j = i; j>0; j--)
Swap(A[j],A[j-1]);
n -= i;
}

B*12011-08-31 07:08

4 楼

i thought the same way as you. Not sure whether it is right.

f*t2011-08-31 07:08

5 楼

我觉得是对的

【在 s**x 的大作中提到】

: say array A[0..(k-1)] contains k numbers
: while (n)
: {
: x = min(n, k-1)
: find i: 0<=i<=x such that A[i] is max among A[0..x]
: for (j = i; j>0; j--)
: Swap(A[j],A[j-1]);
: n -= i;
: }

s*x2011-08-31 07:08

6 楼

sorry forgot to take care of a few conditions:
for (m=0; m0; m++)
{
x = min(n, k-m-1)
find i: m<=i<=x such that A[i] is max among A[m..x]
for (j = i; j>m; j--)
Swap(A[j],A[j-1]);
n -= i;
}