2013-05-11 181 views
2

以下是我正在試圖解決的問題的集合的元素的所有組合: 我給定一組具有斜率m和常數c線。現在我需要找到在y軸右側相交的這些線的交點數。這實質上意味着,對於線路1和2尋找滿足特定條件

    c1>c2 and m2>m1 

我需要計數的交點上Y軸的右側的總數(如果算法存在)一個O(nlogn)算法。我總是可以用蠻力來獲得o(n2)算法,但我正在尋找更快的算法。

+0

您的意思是哪個路口?在第1行和第2行之間?或者在線和X軸之間? – 2013-05-11 07:59:22

+0

我需要找出給定集合中位於x = 0右側的行之間的交點數。 – Malice 2013-05-11 08:24:09

+0

如果您創建根據您的標準排序的行列表,會發生什麼情況?然後,您可以遍歷列表並總結列表條目的數量。複雜度O(n log(n)) – 2013-05-11 08:30:22

回答

3

兩個已排序的向量將做到這一點。

  1. 推所有的線到矢量V1。
  2. 按常數排序v1。之後,v1 [0]是最小c的行。
  3. Traversal v1從開始到結束。對於v1中的每個元素e,我們只應考慮之前訪問的元素(c1> c2)。現在的任務是在所有被訪問的元素中找到m2> m1的元素。
  4. 所以我們只是將已經訪問過的元素推入向量v2中。每次插入後,我們應該按照斜率m對它進行排序(自我平衡BST將完成此任務)。由於v2是按m排序的,二叉搜索會告訴你有多少元素滿足m2> m1。

排序爲n日誌ñ。

插入到v2是log n(它可以通過自平衡BST來實現,並且它會調用n次)。

二進制搜索日誌N(調用n次)。

所以這是O(n日誌n)的

如果你寫在C++,它會像那個(我不定義V2,因爲你要實現一個自平衡BST):

struct line 
{ 
    int c,m; 
    line(int a,int b):c(a),m(b){} 
    bool operator <(const line &a) const 
    { 
     return m>a.m; 
    } 
}; 
bool cmp(const line &v1,const line &v2) 
{ 
    return v1.c<v2.c; 
} 
int main() 
{ 
    vector<line> v1; 
    v1.push_back(line(1,3)); 
    v1.push_back(line(4,1)); 
    v1.push_back(line(3,1)); 
    v1.push_back(line(2,2)); 
    sort(v1.begin(),v1.end(),cmp); 
    int ans=0; 
    for(int i=0;i<v1.size();i++) 
    { 
     int num=v2.find(v1[i]);//return the number of element whose m is larger than v1[i]. 
     ans+=num; 
     v2.insert(v1[i]);// in every step, the element e in v2 will satisfy e.c<v1[i].c 
    } 
    cout << ans; 
} 

這就是全部。如果您有任何問題,請給我留言。

+0

你能否詳細說明步驟3?第4步應該爲每個屬於v1的c做對嗎? – Malice 2013-05-11 08:51:00

+0

如何插入v1 logn?它應該是至少O(n)如果我沒有錯(你必須訪問n個元素來插入它們) – Malice 2013-05-11 08:53:01

+0

@Malice將它插入到v2。在STL :: SET中插入一個元素是log n。而STL :: Set可以被視爲一個排序的向量。 – Sayakiss 2013-05-11 08:55:34

-1

在最壞的情況下,這個問題保證需要O(n^2)操作。

猜我畫一條線,那麼就不可能有交點。我可以在一個獨特的點繪製一條與該線相交的線。現在我可以畫一條與前面兩條線相交的線。我可以繼續繪製與前一行相交的線條。

這意味着的交叉點的數目可達到:

1 + 2 + 3 + 4 + 5 + ... + n-1個

鑑於大小n行的輸入時,尺寸的這個問題的輸出可能是(N *(N-1))/ 2個點或大約N的平方大於2.

因此,即使只是輸出正確的答案,在最壞的情況下也需要O(n^2)。

編輯,忽略之前,我以爲你想要的實際交點,而不僅僅是計數。

+0

我們只關心交點的數量。輸出是一個數字。 – Sayakiss 2013-05-11 08:45:41

0

我張貼我的解決方案,因爲我覺得它更容易實現:

比方說,你得到了線的對象,以下屬性定義:

- m (slope, initialized on start) 
- c (constant, initialized on start) 
- pos_m (default 0 value) 
- pos_c (default 0 value) 

現在,你有一個V這些線的向量,則:通過在元件使用鍵m

  1. 排序V(O(nlogn))。
  2. 迭代V,索引i集合V[i].pos_m = i(O(n))。
  3. 通過在元素(O(nlogn))上使用密鑰cV進行排序。
  4. 迭代V,索引i集合V[i].pos_c = i。 (上))。
  5. result = 0現在V指數迭代iresult += | V[i].pos_m - V[i].pos_c |(O(n))的

分揀,如果比較的值等於再使用其他主要的決定的順序(如果兩者相等,它們是同一條線)。例如,如果在1.兩條線上得到相同的斜率,則讓常數成爲決定因素。