有人用过好使的 shampoo and shower gel２合１吗？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Fashion - 美丽时尚

有人用过好使的 shampoo and shower gel２合１吗？

有人用过好使的 shampoo and shower gel２合１吗？# Fashion - 美丽时尚

d*32010-09-07 07:09

1 楼

Given an array of size n, the array contains numbers in range from 0 to k-1
where k is a positive integer and k <= n. Find the maximum repeating number
in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2,
2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2.
Expected time complexity is O(n) and extra space allowed is O(1).
Modifications to array are allowed.

E*r2010-09-07 07:09

2 楼

☆─────────────────────────────────────☆
ridgeren (Ridge) 于 (Wed Dec 2 11:09:10 2009, 美东) 提到:
很少来股版，最近那个BSO自己狗屎运的家伙跳得很凶，天天上十大，还把自己捧
成penny高手，动不动就是你们蓝筹怎么怎么。其实分歧根本不在于penny还是蓝筹。我
不信penney版的人都像他那样毫无风险控制，一味地死捂加补仓。
我10年前也是这样，迷信基本面，只买自己熟的，入市后不久就碰到网络泡沫，还
有911，然后就只好死捂加补仓。印象最深的是SUNW从40多跌到10几中间我都加过仓，
那时候Java正跑火，IBM，BEA这些又推波助澜，觉得早晚SUN弄出个Hardware JVM出来
我就翻身了，可谁知它那么不争气，当然我没执著到email COO的地步。还有另外几只
不谈也罢。好在我没把全部积蓄扑进去，差不多亏掉一辆DFBB，剩几千块cash out出来
打算金盆洗手。
又过了两年，听一朋友说他的大学上铺兄弟，跟咱同行，99年不幸被雷，回家抱孩
子之余，写了个

g*a2010-09-07 07:09

3 楼

以前买过强生的
感觉一般

s*e2010-09-07 07:09

4 楼

感觉是通过某种方法将出现次数和array的index结合起来，然后再扫视一遍array求最
大值就可以了。

d*32010-09-07 07:09

5 楼

Require Space O(1). 再想想。思路是对的。

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

: 感觉是通过某种方法将出现次数和array的index结合起来，然后再扫视一遍array求最
: 大值就可以了。

z*g2010-09-07 07:09

6 楼

因为 k放在A[i]中，但是要注意的是在放之前确定A[i]是否之前已经被改动过，如果改动过就
直接加，如果没有那么就要while loop了。
例如：
int tmp = 0;
for(int i=0;i{
if(A[i]<0)
{
continue;
}
else
{
tmp = A[i];
A[i] = 0;
while(A[tmp]>=0 && tmp >i) // all A[k] for k<=i has been modified;
{
int tmp2 = A[tmp];
A[tmp] = -1;
tmp = tmp2;
}
A[tmp] -= 1;
}
}
然后找那个A[i]最小的数，输出i。
不知道这个方法可不可以。

1
number
2,
.

【在 d******3 的大作中提到】

: Given an array of size n, the array contains numbers in range from 0 to k-1
: where k is a positive integer and k <= n. Find the maximum repeating number
: in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2,
: 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2.
: Expected time complexity is O(n) and extra space allowed is O(1).
: Modifications to array are allowed.

s*e2010-09-07 07:09

7 楼

其实和那个find the first missing positive相似

o*n2010-09-07 07:09

8 楼

a=[1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3]
k=9
m=[0]*(k+1)
max=0
s=0
for item in a:
m[item] +=1
for j in m:
if j >max :
max = j
s=m.index(j)
print m
print max, s
这个？

E*m2010-09-07 07:09

9 楼

m 不是 O(1)

【在 o*****n 的大作中提到】

: a=[1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3]
: k=9
: m=[0]*(k+1)
: max=0
: s=0
: for item in a:
: m[item] +=1
: for j in m:
: if j >max :
: max = j

l*n2010-09-07 07:09

10 楼

inplace counting，用0~(k-1)的位置记录相应的数字的个数。不过在此之前要先把0~(
k-1)的位置置换好。

h*g2010-09-07 07:09

11 楼

for(int i=0;iif(A[i]==i)
continue;
else if(A[A[i]]!=A[i]){
swap(A[i],i);
}
else{
A[A[i]]+=A[i];
}
}
目标是A[i]=i, 如何不相等，就把它换到正确的位置，换之前要考察要换到的这个位置
上有没有正确的数，如果没有就直接换，否则就不换而是加上去。比如 {0,1,1} A[2]
要换到index=1的位置上，这个位置上已经有1了就加上去，变成{0,2,1}.
最后再扫描一遍算m=A[i]/i的最大值。上例中A[1]=2 因此1出现了2次，是最多的

x*92010-09-07 07:09

12 楼

k，属于个例

1
number
2,
.

【在 d******3 的大作中提到】

c*e2010-09-07 07:09

13 楼

Swap有个while loop
最后一个else的和还可能是小于K的
因此要用特殊的数表示发生的次数，例如K，K+1。。。
check A[i]是否已做过统计如果a[i] >= k, 则跳过
A[i]==i, setA[i]=k

【在 h****g 的大作中提到】

: for(int i=0;i: if(A[i]==i)
: continue;
: else if(A[A[i]]!=A[i]){
: swap(A[i],i);
: }
: else{
: A[A[i]]+=A[i];
: }
: }

d*32010-09-07 07:09

14 楼

想法很好，但行不通。A = {0, 1, 4, 1, 1} 就不行了。

【在 h****g 的大作中提到】

: for(int i=0;i: if(A[i]==i)
: continue;
: else if(A[A[i]]!=A[i]){
: swap(A[i],i);
: }
: else{
: A[A[i]]+=A[i];
: }
: }

d*32010-09-07 07:09

15 楼

kn也能做出来的。

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

: k: ，属于个例
:
: 1
: number
: 2,
: .

c*e2010-09-07 07:09

16 楼

k>=n 可能就没重复了

【在 d******3 的大作中提到】

: kn也能做出来的。

c*e2010-09-07 07:09

17 楼

public int findMaximumRepeated(int[] arr, int k) {
countNumbers(arr, k);

for(int i = k-1; i >=0; i--) {
if(arr[i] > k) {
return i;
}
}
return -1;
}

public void countNumbers(int[] arr, int k) {
for(int i = 0; i < arr.length; i++) {
if(arr[i] >= k) {
continue;
}else if(arr[i] == i) {
arr[i] = k;
} else {
while (true) {
if(arr[i] == arr[arr[i]]) {
arr[arr[i]] = k+1;
break;
}else if(arr[arr[i]] >= k) {
arr[arr[i]] += 1;
break;
}else {
int temp = arr[arr[i]];
arr[arr[i]] = k;
arr[i] = temp;
}
}
}
}
}

1
number
2,
.

【在 d******3 的大作中提到】

d*32010-09-07 07:09

18 楼

大家注意，增加难度喽："The original array should be recovered in the end."

c*e2010-09-07 07:09

19 楼

那就没发现一个数就加N然后arr[i]%n就是原来的数，arr[i]/n就是发生的次数

【在 d******3 的大作中提到】

: 大家注意，增加难度喽："The original array should be recovered in the end."

d*32010-09-07 07:09

20 楼

Good thinking. 加油。俺先睡了。

【在 c********e 的大作中提到】

: 那就没发现一个数就加N然后arr[i]%n就是原来的数，arr[i]/n就是发生的次数

c*e2010-09-07 07:09

21 楼

arr里面数字还是要0~n-1 (k<=n) 之间的，否则是无法统计的.话说这题很像某人的待字
闺中的一道题
public int findMaximumRepeated(int[] arr) {
countNumbers(arr);
int max = findMaximum(arr);
recoverArr(arr);
return max;
}

public void recoverArr(int[] arr) {
int n = arr.length;
for(int i = 0; i < n; i++) {
arr[i] %= n;
}
}

public int findMaximum(int[] arr) {
int n = arr.length;
for(int i = n-1; i >=0; i--) {
if(arr[i]/n > 1) {
return i;
}
}
return -1;
}
public void countNumbers(int[] arr) {
int n = arr.length;
for(int i = 0; i < n; i++) {
int num = arr[i]%n;
arr[num] += n;
}
}

【在 d******3 的大作中提到】

: 大家注意，增加难度喽："The original array should be recovered in the end."

r*n2010-09-07 07:09

22 楼

1. partition by some value into sub array A and sub array B.
2. if A.length-(max(A)-min(A)) larger than B.length-(max(B)-min(B))
then keep sub array A, otherwise keep sub array B.
3. repeat step 2 until the sub array has all same elements.

1
number
2,
.

【在 d******3 的大作中提到】

d*k2010-09-07 07:09

23 楼

Obviously wrong.
1 1 2 2 3 3 4 5 6 6 6

【在 r*******n 的大作中提到】

: 1. partition by some value into sub array A and sub array B.
: 2. if A.length-(max(A)-min(A)) larger than B.length-(max(B)-min(B))
: then keep sub array A, otherwise keep sub array B.
: 3. repeat step 2 until the sub array has all same elements.
:
: 1
: number
: 2,
: .

d*k2010-09-07 07:09

24 楼

很赞！
楼主说k <= n不是必须，还请楼主来说明下
感谢分享

待字

【在 c********e 的大作中提到】

: arr里面数字还是要0~n-1 (k<=n) 之间的，否则是无法统计的.话说这题很像某人的待字
: 闺中的一道题
: public int findMaximumRepeated(int[] arr) {
: countNumbers(arr);
: int max = findMaximum(arr);
: recoverArr(arr);
: return max;
: }
:
: public void recoverArr(int[] arr) {

r*n2010-09-07 07:09

25 楼

thanks!

【在 d*k 的大作中提到】

: Obviously wrong.
: 1 1 2 2 3 3 4 5 6 6 6

b*e2010-09-07 07:09

26 楼

This is cheating. You are widening each integer size, which is basically
allocating another array. The space complexity is in strictly O(n) for this
algorithm.

待字

【在 c********e 的大作中提到】

e*w2010-09-07 07:09

27 楼

数组所有的数都是0～k-1，因此只要从头到尾扫一遍，看到a.i就让a.(a.i % k)加个k.
然后再扫一遍整个数组，最大的那个a.j，那么j就是重复最多的数。
还原数组只要再扫一遍数组，a.i %= k.
当然实际实现时候后面两个操作可以并作一步扫完。

1
number
2,
.

【在 d******3 的大作中提到】

e*w2010-09-07 07:09

28 楼

啊没看到已经有解了。

待字

【在 c********e 的大作中提到】

d*32010-09-07 07:09

29 楼

我想漏了，k<=n还是必须的。小眼睛的是正解。

【在 d*k 的大作中提到】

: 很赞！
: 楼主说k <= n不是必须，还请楼主来说明下
: 感谢分享
:
: 待字

g*s2010-09-07 07:09

30 楼

debugged code. The other solutions are not complete. Any solution shorter
than this one is wrong.
int maxRepeatedNumber(int A[], int n, int k)
{
assert(k <= n);
int i;
//replace values with occurrence
for(i = 0; i < n; i++)
{
int val = A[i];
if(val < n) //not touched
{
A[i] = (val+1)*n; //initialization, means occurrence of i is
0
//put val
for(;;)
{
int cur = A[val];
if(cur < n) //not touched
{
A[val] = (cur+1)*n + 1;
val = cur;
}
else
{
A[val]++;
break;
}
}
}
}
//find the maximum repeating number
int maxIdx = 0;
for(i = 1; i < n; i++)
{
if((A[maxIdx]%n) < (A[i]%n))
maxIdx = i;
}

//recover original array
for(i = 0; i < n; i++)
{
A[i] = A[i]/n - 1;
}
return maxIdx;
}