在行中搜索明智排序的2D n x n矩陣

如何搜索行中明智排序的元素n n n矩陣。可以在O(nlogn)中通過對每行使用二進制搜索和O(nlog(logn))通過對每行使用內插搜索來完成。任何O(n)解決方案？在行中搜索明智排序的2D n x n矩陣

約束：數組包含整數。

示例：在給定的5x5矩陣中搜索32。

0 5 6 8 42 98 

-4 -1 3 21 455 

-4 0 3 4 4 

0 0 0 0 0 

0 [32] 64 244 333

請幫忙。

來源

2013-10-17 Rajarshi Sarkar

行被排序，但列不是。所以O（n）是不可能的。 –

那麼，最好的O（nlog（logn））？ –

您的示例不包含任何額外的值。另外，第二行沒有排序。 –

搜索x矩陣M [m * n]（m行，n列）。
我認爲最好的選擇是不正確的跳行。
- 如果x超出行（R）的範圍內，那麼跳過該簡單地套用二進制（或指數位近似值）的頂級搜索

const int n=...; 
const int m=...; 
double x=...,A[m][n]={...}; 
int r,i,j,j0; 
double *p; 
// init bit mask for index approximation 
for (j=1;j<n;j<<=1); j>>=1; if (!j) j=1; j0=j; 
// search 
for (r=0;r<m;r++) // all rows 
if (x>=A[r][0]) // skip if x is too low 
    if (x<=A[r][n-1]) // skip if x is too high 
    { 
    // index approximation search in row r 
    for (p=A[r],i=0,j=j0;j;j>>=1) 
    { 
    i|=j; 
    if ((i>=n)||(x<p[i])) i^=j; 
    if (x==p[i]) return "x found in A[r][i]"; 
    } 
    } 
return "x not found";

在複雜
而且搜索它的N是M * n和算法是：

Omin(m+ log2(n)) 
Omax(m+m*log2(n))

如果（M == n）的話，可以在N = N * N順序更簡單地重寫它：

Omin(sqrt(N)+ log2(sqrt(N))) 
Omax(sqrt(N)*(1+log2(sqrt(N))))

如果沒有則N-> N/m和M-> N/N，以便：

Omin((N/n)+ log2(sqrt(N/m))) 
Omax((N/n)*(1+log2(sqrt(N/m))))

正如你可以看到複雜性上矩陣值強烈依賴和從10min爲單位進行到OMAX。程序應該改變以符合你的界面和環境，並且返回值只是爲了顯示發生了什麼，應該改變以滿足你的需求。

來源

2013-10-19 08:14:25 Spektre

-1

雖然是一個相當舊的帖子，但仍然。

從右上角或左下角開始（任何一邊都可以選擇）。假設我們選擇右上角。將鍵與矩陣元素進行比較。 O（n + n）= O（n）。最壞情況下的時間複雜度是當我們需要移動一個完整的行和一個完整的列時，O（n + n）= O（n）。

來源

2016-11-04 09:52:08

在行中搜索明智排序的2D n x n矩陣

回答

相關問題