剛看到的一個(gè)排序算法題，大家討論討論。

emacsnw

原帖由 ArXoR 于 2006-12-28 20:42 發(fā)表


如果數(shù)組是浮點(diǎn)數(shù), 但是題目保證輸入都是整數(shù)的話, 利用小數(shù)部分保存信息可以做到O(n)...
但是有點(diǎn)cheat了...

這個(gè)有點(diǎn)意思，不妨說來聽聽，呵呵。

bleem1998

原帖由 tyc611 于 2006-12-29 13:31 發(fā)表

你這樣做，第一遍之后就把剩下的子序列打亂了，不知道你怎么處理剩下的

我想只需要做一遍就可以了
一個(gè)for搞定

ArXoR

原帖由 emacsnw 于 12/29/06 13:35 發(fā)表


這個(gè)有點(diǎn)意思，不妨說來聽聽，呵呵。

就是首先, 問題的最優(yōu)解等于序列中元素的最大重復(fù)數(shù), 這個(gè)容易證明.

然后我們考慮下面這個(gè)簡(jiǎn)單的情形:

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

復(fù)制代碼

不嚴(yán)格的說:
我們每次只需要把這個(gè)形狀的天空線, 打印出來就行了
打印出來的值就刪掉, 比如輸出一個(gè)子序列后變成下面這樣:

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

復(fù)制代碼

要實(shí)現(xiàn)這個(gè),
我們維護(hù)一個(gè)鏈表, 這個(gè)鏈表就是當(dāng)前這次掃描應(yīng)該輸出序列(不好意思...要描述還真是e...)
鏈表用Pi表示.

比如初始的時(shí)候P1=4, P4=5, P5=7, P7=8, P8=-1

然后每次輸出元素的時(shí)候維護(hù)這個(gè)指針序列就行了, 檢查一下是否對(duì)應(yīng)的值已經(jīng)用完, 沒完就加1, 完了就推進(jìn), 相當(dāng)于從鏈表中刪掉結(jié)點(diǎn), 設(shè)當(dāng)前待輸出子序列長度為k, 維護(hù)復(fù)雜度是O(k)的
由于每個(gè)元素最多被刪一次, 用平攤分析可以得到輸出完成的復(fù)雜度是O(n)
還可以添加一個(gè)在0位置的頭元素, P0始終指向鏈表頭, 方便統(tǒng)一處理.
而且初始的Pi可以在O(n)里完成

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

不考慮浮點(diǎn)誤差的話...應(yīng)該可以這樣...

BTW: 如果直接打印也算輔助空間的話...暫時(shí)沒轍了
cheat啊~~

Please correct me if I'm wrong.

emacsnw

原帖由 ArXoR 于 2006-12-28 22:12 發(fā)表


就是首先, 問題的最優(yōu)解等于序列中元素的最大重復(fù)數(shù), 這個(gè)容易證明.

然后我們考慮下面這個(gè)簡(jiǎn)單的情形:

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

復(fù)制代碼

不嚴(yán)格的說:
我們每次只需要把這個(gè)形狀 ...

這個(gè)需要的空間不是O(1)的。

ArXoR

原帖由 emacsnw 于 12/29/06 14:28 發(fā)表


這個(gè)需要的空間不是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++;
        }
}


請(qǐng)高人指正！

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

大家興致這么高，索性也寫一個(gè)。有比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. }
    

復(fù)制代碼

apirl

這個(gè)用python來寫復(fù)雜度怎么算啊？

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. 
    

復(fù)制代碼

沙灘

我想了半天也只想出 crspo  圣騎士 的辦法