以下是我正在試圖解決的問題的集合的元素的所有組合: 我給定一組具有斜率m和常數c線。現在我需要找到在y軸右側相交的這些線的交點數。這實質上意味着,對於線路1和2尋找滿足特定條件
c1>c2 and m2>m1
我需要計數的交點上Y軸的右側的總數(如果算法存在)一個O(nlogn)算法。我總是可以用蠻力來獲得o(n2)算法,但我正在尋找更快的算法。
以下是我正在試圖解決的問題的集合的元素的所有組合: 我給定一組具有斜率m和常數c線。現在我需要找到在y軸右側相交的這些線的交點數。這實質上意味着,對於線路1和2尋找滿足特定條件
c1>c2 and m2>m1
我需要計數的交點上Y軸的右側的總數(如果算法存在)一個O(nlogn)算法。我總是可以用蠻力來獲得o(n2)算法,但我正在尋找更快的算法。
兩個已排序的向量將做到這一點。
排序爲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;
}
這就是全部。如果您有任何問題,請給我留言。
在最壞的情況下,這個問題保證需要O(n^2)操作。
猜我畫一條線,那麼就不可能有交點。我可以在一個獨特的點繪製一條與該線相交的線。現在我可以畫一條與前面兩條線相交的線。我可以繼續繪製與前一行相交的線條。
這意味着的交叉點的數目可達到:
1 + 2 + 3 + 4 + 5 + ... + n-1個
鑑於大小n行的輸入時,尺寸的這個問題的輸出可能是(N *(N-1))/ 2個點或大約N的平方大於2.
因此,即使只是輸出正確的答案,在最壞的情況下也需要O(n^2)。
編輯,忽略之前,我以爲你想要的實際交點,而不僅僅是計數。
我們只關心交點的數量。輸出是一個數字。 – Sayakiss 2013-05-11 08:45:41
我張貼我的解決方案,因爲我覺得它更容易實現:
比方說,你得到了線的對象,以下屬性定義:
- m (slope, initialized on start)
- c (constant, initialized on start)
- pos_m (default 0 value)
- pos_c (default 0 value)
現在,你有一個V
這些線的向量,則:通過在元件使用鍵m
V
(O(nlogn))。V
,索引i
集合V[i].pos_m = i
(O(n))。c
對V
進行排序。V
,索引i
集合V[i].pos_c = i
。 (上))。result = 0
現在V
指數迭代i
做result += | V[i].pos_m - V[i].pos_c |
(O(n))的分揀,如果比較的值等於再使用其他主要的決定的順序(如果兩者相等,它們是同一條線)。例如,如果在1.兩條線上得到相同的斜率,則讓常數成爲決定因素。
您的意思是哪個路口?在第1行和第2行之間?或者在線和X軸之間? – 2013-05-11 07:59:22
我需要找出給定集合中位於x = 0右側的行之間的交點數。 – Malice 2013-05-11 08:24:09
如果您創建根據您的標準排序的行列表,會發生什麼情況?然後,您可以遍歷列表並總結列表條目的數量。複雜度O(n log(n)) – 2013-05-11 08:30:22