刚看到的一个排序算法题，大家讨论讨论。

emacsnw

原帖由 ArXoR 于 2006-12-28 20:42 发表


如果数组是浮点数, 但是题目保证输入都是整数的话, 利用小数部分保存信息可以做到O(n)...
但是有点cheat了...

这个有点意思，不妨说来听听，呵呵。

bleem1998

原帖由 tyc611 于 2006-12-29 13:31 发表

你这样做，第一遍之后就把剩下的子序列打乱了，不知道你怎么处理剩下的

我想只需要做一遍就可以了
一个for搞定

ArXoR

原帖由 emacsnw 于 12/29/06 13:35 发表


这个有点意思，不妨说来听听，呵呵。

就是首先, 问题的最优解等于序列中元素的最大重复数, 这个容易证明.

然后我们考虑下面这个简单的情形:

1. 
   
2. 1
   
3. 1      3      5
   
4. 1  2  3  4  5
   

复制代码

不严格的说:
我们每次只需要把这个形状的天空线, 打印出来就行了
打印出来的值就删掉, 比如输出一个子序列后变成下面这样:

1. 
   
2. 
   
3. 1            
   
4. 1     3     5
   

复制代码

要实现这个,
我们维护一个链表, 这个链表就是当前这次扫描应该输出序列(不好意思...要描述还真是e...)
链表用Pi表示.

比如初始的时候P1=4, P4=5, P5=7, P7=8, P8=-1

然后每次输出元素的时候维护这个指针序列就行了, 检查一下是否对应的值已经用完, 没完就加1, 完了就推进, 相当于从链表中删掉结点, 设当前待输出子序列长度为k, 维护复杂度是O(k)的
由于每个元素最多被删一次, 用平摊分析可以得到输出完成的复杂度是O(n)
还可以添加一个在0位置的头元素, P0始终指向链表头, 方便统一处理.
而且初始的Pi可以在O(n)里完成

就是基于上面的算法, 可以看到Pi有界, 在[-1,n]中, 我们把小数部分分成[n+2]段, 就可以附加保存Pi了...

不考虑浮点误差的话...应该可以这样...

BTW: 如果直接打印也算辅助空间的话...暂时没辙了
cheat啊~~

Please correct me if I'm wrong.

emacsnw

原帖由 ArXoR 于 2006-12-28 22:12 发表


就是首先, 问题的最优解等于序列中元素的最大重复数, 这个容易证明.

然后我们考虑下面这个简单的情形:

1. 
   
2. 1
   
3. 1      3      5
   
4. 1  2  3  4  5
   

复制代码

不严格的说:
我们每次只需要把这个形状 ...

这个需要的空间不是O(1)的。

ArXoR

原帖由 emacsnw 于 12/29/06 14:28 发表


这个需要的空间不是O(1)的。

嗯, 所以说是cheat...

nli_224

void divide_arr(int a[],int n){
        int i,j,cur,tmp;
        cur=0;
        while(cur<n){
            for(i=cur+1;i<n;i++){
                if(a[i]>a[cur]){
                    tmp=a[i];
                    for(j=i;j>=cur+1;j--)
                        a[j]=a[j-1];
                    a[cur+1]=tmp;
                    break;
                }

            }
            cur++;
        }
}


请高人指正！

broadoceans

#include <iostream>
using namespace std;
void sort(int a[], int n)
{
        int cur = 0;
        int pos;
        int temp;
        pos = cur + 1;
        while(cur < n)
        {       
                if(pos >= n) //不需要每次都重新搜索
                        pos = cur + 1;
                for(; pos < n; ++pos)
                {
                        if(a[pos] > a[cur])
                        {
                                temp = a[pos];
                                for(int i = pos; i > cur + 1; --i)
                                        a[i] = a[i - 1];
                                a[cur + 1] = temp;
                                break;
                        }
                }               
                cur++;
        }
}
void main()
{
        int a[] = {1, 1, 1, 2, 3, 3, 4, 5, 5};
        int n = sizeof(a) / sizeof(int);
        sort(a, n);
        for(int i = 0; i < n; ++i)
        {
                cout << a[i] << " ";
        }
        cout << endl;
       
}

crspo

大家兴致这么高，索性也写一个。有比O(n^2)更快的吗？

1. 
   
2. void unique(int a[],int n)
   
3. {
   
4.   int i=0,j,k,m;
   
5.   while(i<n){
   
6.     k=0;
   
7.     j=i+1;
   
8.     while(j<n){
   
9.       if(a[j]==a[i])
   
10.         k++;
    
11.       else
    
12.         a[j-k]=a[j];
    
13.       j++;
    
14.     }
    
15.     for(j=n-k;j<n;j++)
    
16.       a[j]=a[i];
    
17.     i++;
    
18.   }     
    
19. }
    

复制代码

apirl

这个用python来写复杂度怎么算啊？

1. 
   
2. a=[1,1,1,2,3,3,4,5,5]
   
3. i = 0
   
4. b=len(a)
   
5. while i<b:
   
6.       if a[i:i+1] == a[i+1:i+2]:
   
7.         a[i:] = a[i+2:]+a[i:i+1]
   
8.      i=i+1
   
9. 
   
10. 
    

复制代码

沙滩

我想了半天也只想出 crspo  圣骑士 的办法