更改數組中的位

我有一個位數組。位將根據以下標準切換和打開： 1.如果位左側和右側的位打開，則該位爲1，否則爲零。 2.邊界條件（最左邊和最右邊的位將只用以下標準依賴於一個比特。即，或者左的它或它的右邊。更改數組中的位

此陣列將被處理m次。

我寫的下面的代碼中，A是原始數組，subsiquent是處理數組，但是這會給我O（nm），其中n是長度，m是我想要執行該過程的次數。這樣我就可以減少我的複雜性了。

for(int k = 0;k < m;k++){ 
    for(int l = 0;l < n;k++){ 
    if(l == 0){ 
     if(A[l+1]==1) 
     subsiquent[l]=1; 
     else 
     subsiquent[l]=0; 
     //** is there a } missing here? 
     else if(l==n){ 
     if(A[l-1]==1) 
      subsiquent[l]=1; 
     else 
      subsiquent[l]=0;       
     } else { 
     if(A[l+1]==1 && A[l-1]==1){ 
      subsiquent[l]=1; 
     }else{ 
      subsiquent[l]=0; 
     } 
     } 
    //** or is there a } missing here?  
    } 

    A = subsiquent; 
}

來源

2017-08-10 ketan anand

要掃描'N'位'M'次？我懷疑O（n * m）以下的複雜度可能會顯着降低。 – Thomas

所以你建議沒有其他解決方案可以切換。除了掃描m次之外，不能做任何事情來進行切換嗎？謝謝 –

@ketananand你爲什麼要掃描m次？ –

有些事情要看：

如果你最後一個第一個或最後一個比特是0，它們將始終保持爲0，所以比特p + 1（resp。 p-1）。所以你可以添加一個檢查，並減少你的循環的開始/結束（並將p + 1數字更改爲0）
同樣，如果p first（resp last）數字是1，那麼p-1數字將停留在1和位p將爲0
我已經全部爲零或全部爲1，不需要更改需要
同樣的事情可以在你的數組中間完成（中間是5個零？下一次是7，五個1？三個中間將保持1），但不確定它很容易整合（只有當你說1000個相同位是值得處理它我認爲）
如果你沒有結束對所有0或全1，你將有一個0和1的交替。所以你也可以檢查你是否交替0和1，並用模2重新maining米，可以預測結果

編輯：具有p>在我爲當然四肢例子= 2

編輯：可以表示在一個int數組的數組作爲相似的比特數+記住第一位 000111101100110101將表示爲[0] 3412221111（從零開始，然後是3零，然後是4，然後是1，然後是2，等等）

我沒有檢查全部，但你可以用最小的步驟輕鬆地推斷出一步到另一步的規則。（有很多情況下，我讓你找到它們，你只需要從左到右，記住你從0和1切換，但是迭代或者插入數字時可能需要修改/減少右邊的數字。鏈表將在這裏非常適合）

例如，步驟是：

000111101100110101 [0]3-4-1-2-2-2-1-1-1-1  
000011010000001010 [0]4-2-1-1-6-1-1-1-1 
000000100000000101 [0]6-1-8-1-1-1 
000000000000000010 [0]16-1-1 
000000000000000001 [0]17-1 
000000000000000000 [0]18

來源

2017-08-10 08:59:37 Treziac

感謝您的幫助 –

更改數組中的位

回答

相關問題