將子陣列轉移到同一陣列中的另一個位置，沒有臨時變量

-1

我可以在不使用任何臨時變量的情況下將子陣列轉移到同一陣列中的另一個位置嗎？例如：將子陣列轉移到同一陣列中的另一個位置，沒有臨時變量

input array = {1,2,3,4,5,6} 
Task = Shift {2,3} to index 4 
Output array = {1,4,5,6,2,3}

我能想到的唯一方法就是以某種方式使用多次交換，這可能會導致所需的輸出。我正在尋找一種可以減少掉期數量的策略。

歡迎任何其他關於如何實現這一點的建議，無論是否進行多次交換。

解決方案由@ free6om建議：

static void shiftArray(int[] array, int i, int n, int j) { 
     int count = (j - i - 1)/n; 
     for (int p = 0;p < count;p++) { 
      for (int q = 0;q < n;q++) { 
       swap(array, i + p*n + q, i + (p+1)*n + q); 
      } 
      } 

      for (int q = 0;q < n;q++) { 
      swap(array, i + count*n + q, j + q); 
      } 
    } 

    static void swap(int[] array, int i, int j) { 
      array[i] = array[i] + array[j]; 
      array[j] = array[i] - array[j]; 
      array[i] = array[i] - array[j]; 
    }

來源

2016-03-25 Minaxi Singla

你確定你不想使用*任何*臨時變量（這是一個任意的和稍微愚蠢的限制，因爲編譯器會優化變量，當它只用於交換）？還是隻是你不想使用臨時數組（這是明智的，因爲臨時數組的大小可能幾乎與原始數組一樣大）？ – hyde

@hyde不，我不想使用任何臨時變量。我同意編譯器會優化變量，但我有興趣在不使用自己的顯式臨時變量的情況下實現它。 –

好的，沒關係。你可能想澄清一下，如果你對數組轉換感興趣，或者只是[this]（https://en.wikipedia.org/wiki/XOR_swap_algorithm）。我認爲這種轉變。添加你當前（天真？）的子陣列轉換實現也將有助於解決這個問題。 – hyde

爲您更新：
最小掉期((j - i - 1)/n) * n，其中i是子數組的頭索引，j是目標指數，n是子陣列的長度。
一種策略來實現這一目標：

void shiftArray(int[] array, int i, int n, int j) { 
    int count = (j - i - 1)/n - 1; 
    for (int p = 0;p < count;p++) { 
     for (int q = 0;q < n;q++) { 
      swap(array, i + p*n + q, i + (p+1)*n + q); 
     } 
    } 

    for (int q = 0;q < n;q++) { 
     swap(array, i + count*n + q, j + 1 - n + q); 
    } 

}

原來的答覆：
關鍵點是交換無臨時變量，這裏是代碼：

void swap(int[] array, int i, int j) { 
    array[i] = array[i] + array[j]; 
    array[j] = array[i] - array[j]; 
    array[i] = array[i] - array[j]; 
}

來源

2016-03-25 05:23:01 free6om

我很感激你提供的交換代碼沒有臨時變量。似乎我的問題沒有說明我在找什麼。更改問題描述。 –

我接受您的解決方案，因爲它使用非常小的編輯。從計數值中刪除-1，即將其更改爲（j-i-1）/ n。 –

好free6om了大部分了。

我將重新使用他的交換方法。

void swap(int[] array, int i, int j) { 
    array[i] = array[i] + array[j]; 
    array[j] = array[i] - array[j]; 
    array[i] = array[i] - array[j]; 
}

替代掉..

void swap(int[] array, int i, int j) { 
    if(array[i] == array[j]) 
     continue; 
    array[i] ^= array[j]; 
    array[j] ^= array[i]; 
    array[i] ^= array[j]; 
}

現在，你的問題。

input array = {1,2,3,4,5,6} 
Task = Shift {2,3} to index 4 
Output array = {1,4,5,6,2,3}

indx1需要去indx4和indx2需要去indx5。

swap(array, 1, 4); 
swap(array, 2, 5);

如果您需要做兩個以上的變量，請使用循環或其他東西。您還需要檢查交換是否可能（不希望出現數組越界異常）。

來源

2016-03-25 06:11:11

問題要求將數組轉換爲新索引，不僅交換提到的索引。您的解決方案將輸出{1,5,6,4,2,3}。 –

將子陣列轉移到同一陣列中的另一個位置，沒有臨時變量

回答

相關問題