鑑於陣列[a1b2c3d4]轉換成[ABCD1234]

限制條件：鑑於陣列[a1b2c3d4]轉換成[ABCD1234]

O（1）空間
O（n）的時間

這不是一個家庭作業的問題只是我遇到了一個有趣的問題。

下面是我能想到的一些解決方案，但沒有在給定的限制條件下做到這一點。

方法1

*具有O（N）存儲器*

鴻溝兩個部分遞歸陣列。（對於每個子問題，一直劃分到大小< = 2）
對每個子問題先用數組排序，然後用數字排序。
合併所述子問題陣列

方法2

在爲O（n log n）的時間

排序基於字典順序排列變得1234ABCD
顛倒陣列的兩半4321dcba
逆向整個字符串ABCD1234

方法3

如果號碼的範圍被定義

此外，如果情況是，數字是在特定的範圍內，那麼我可以初始化INT說track = 0; 並設置適當的位，當我遇到數組例如（1 < < a [2]）。 1.交換字母到數組的前半部分 2.標記軌道變量中的數字 3.稍後使用軌道填充數組的後半部分。

方法4 如果我們要刪除的整數的範圍有限，但那麼它將需要更多的內存，我們可以使用方法3 HashMap中。

想不到更好的方法來解決O（1）時間和O（n）空間中的一般問題。

通用這裏的問題是指：

給定一個序列x1y1x2y2x3y3 .... xnyn 其中x1，x2是字母X1 < X2 < .... < XN 和Y1Y2 ... yn是整數。y1 < y2 < .... < yn 排列輸出爲x1x2 ... xny1y2 ... yn

有什麼建議嗎？

來源

2012-10-02 amit modi

你需要弄清楚如何重新排列6個字符不超過8個動作。（但是，如果需要的話，「行爲」可以是多次交換，並且仍然維持秩序N.）（並且請注意，如您所述，問題沒有提及排序，只是將8個字符重新排列爲定義的序列。） –

@熱舔：我試着在這些線上思考，但最終得到的不是通用的解決方案。 1.上半部分的中心元素例如「1b」，所以我們得到ab12c3d4。 2.交換下半部分ab12cd34的中心元素。 3.交換完整陣列abcd1234的中心2元素。但是這種技術只適用於數組的大小是8的倍數。 –

定義「通用」 - 你沒有說明一個通用的問題。你舉了一個例子，但沒有提示如何推廣。 –

什麼是n？假設n是輸入的大小：

這被稱爲列表的卷積。實質上，您必須將(a,1),(b,2),(c,3),(d,4)對的列表轉換爲一對列表(a,b,c,d),(1,2,3,4)。這與矩陣的轉置操作相同。

無論如何，你必須將結構看作一個k維數組，其中k = lg n。數組的卷積是當您將索引i處的值「移動」到索引i按位旋轉時得到的結果。在這種情況下，我們要將索引向右旋轉1位。這意味着卷積是最大週期長度爲k的置換。然後訣竅是從每個循環中選擇一個索引 - 這將始終包括0和n-1。

編輯：其實，你可能想要的是將排列分解成換位產品。那麼，你需要做的就是交換。

來源

2012-10-02 02:52:01

你能舉個例子來解釋一下嗎「數組的卷積是當你」移動「索引i處的值來索引我按位旋轉時得到的結果。」對不起，我沒有得到 –

當n = 8時，k = 3，這意味着排列是（0）（1 4 2）（3 5 6）（7）。 001 => 100 => 010 => 001，等等。您將每個索引轉換爲k位自然數並按位旋轉。有趣的事實：如果你執行卷積k次，你會得到原始數組。 –

Smit：謝謝，我明白了...... awesum algo dude :) –

-3

這是我在O（n）中的算法。

空隙cycle_leader（INT * ARR，INT N） {

for (int i = 1; i < n/2; i+= 2) 
{ 
    int j = i; 
    int save; 
    int tmp = arr[i]; 

    do{ 
     if (j & 1) //odd index element 
      j = n/2 + j/2; 
     else 
      j = j/2; 

     save = arr[j]; 
     arr[j] = tmp; 
     tmp = save; 
    } while(j != i); 
}

}

來源

2014-05-10 03:41:49 coder

n = 12的情況不起作用。使用char數組而不是int數組，示例'cycle_leader（「a0b1c2d3e4f5g6」，12）'給出了「」ae15d04cg3bf26「'。 –

感謝您的評論。是的，這不適用於這種情況。 – coder

解決方案：

首先（索引0）和最後一個（索引n-1）做不動。
總移動次數是（n - 2）
源中的偶數數字元素是字母表。他們進入上半場。

目標=焦耳/ 2 // n爲偶數
在源奇數元素是數字，並且它們移動到第二的一半。

目標= N/2 +地板（J/2）
從1號元素開始，動議到其目標位置。
將您在目標位置找到的內容移動到目標位置等，直到形成循環。注1：有時，循環不包括列表中的所有元素，所以繼續使用j + 2 注2：有時，在一個循環結束時，將實現所需的解決方案，但如果我們繼續，數組將再次被加擾。要解決這個問題，請計算髮生的移動次數，並在達到n - 2時進行減少。

你可以試着運行代碼，克隆和編輯在這裏 Online Java Compiler IDE

int maxShifts = n - 2; // This is required to fix going around and messing up. 
int shifts = 0; 

for (int i = 1; i < n && shifts < maxShifts; i+=2) { 
    int source = i; 
    char itemToMove = array[source]; 
    do { 
    int target; 
    if (source % 2 == 0) { 
     target = source/2; // Even index is an alphabet 
    } else { 
     target = n/2 + source/2; // Odd index is a digit, that goes in the second half 
    } 
    char tmp = array[target]; 
    array[target] = itemToMove; 
    itemToMove = tmp; 

    shifts++; 
    source = target; 

    } while (i != source /*&& shifts < maxShifts*/); // Full cycle reached 

}

來源

2016-04-09 07:43:51 JackDaniels

或者，您可以使用強大的Python和它翻譯成Java：

a = [1,'a',2,'b',3,'c',4,'d'] 
a = a[0:len(a):2] + a[1:len(a):2] 
print(a) #this will print [1,2,3,4,'a','b','c','d']

來源

2016-05-04 11:34:18

鑑於陣列[a1b2c3d4]轉換成[ABCD1234]

回答

相關問題