判斷數組是否可以排序-php教程-PHP中文網

Find if Array Can Be Sorted

3011。判斷數組是否可以排序

難度：中

主題：陣列、位元操作、排序

給你一個0索引數組，其中正整數nums。

在一次操作中，您可以交換任兩個相鄰元素，如果它們具有相同個設定位¹ 。您可以執行此操作任意次（包括零）。

如果可以對陣列進行排序，則傳回 true，否則傳回 false.

範例1：

輸入： nums = [8,4,2,30,15]
輸出： true
解釋： 讓我們看看每個元素的二進位表示。數字2、4和8分別具有一組二進位表示「10」、「100」和「1000」的位元。數字15和30有四個設定位，每個設定位具有二進位表示「1111」和「11110」。我們可以使用 4 個操作對陣列進行排序：
- 將 nums[0] 與 nums[1] 交換。此操作有效，因為 8 和 4 各有一個設定位。數組變成 [4,8,2,30,15].
- 將 nums[1] 與 nums[2] 交換。此操作有效，因為 8 和 2 各有一個設定位。數組變成 [4,2,8,30,15].
- 將 nums[0] 與 nums[1] 交換。操作有效，因為 4 和 2 各有一個設定位。數組變成 [2,4,8,30,15].
- 將 nums[3] 與 nums[4] 交換。此操作有效，因為 30 和 15 各有四個設定位。數組變成 [2,4,8,15,30].
- 陣列已排序，因此我們傳回 true。
- 請注意，可能還有其他操作序列也會對陣列進行排序。

範例2：

輸入： nums = [1,2,3,4,5]
輸出： true
解釋： 陣列已經排序，因此我們傳回 true。

範例 3：

輸入： nums = [3,16,8,4,2]
輸出： false
解釋： 可以證明，不可能使用任意數量的操作來對輸入數組進行排序。

範例 4：

輸入： nums = [75,34,30]
輸出： false
解釋： 可以證明，不可能使用任意數量的操作來對輸入數組進行排序。

約束：

提示：

將陣列分割成段。每個段包含具有相同設定位數的連續元素。
從左到右，前一個段的最大元素應該小於當前段的最小元素。

解：

我們需要確定是否可以透過僅交換二進位表示中具有相同數量的設定位的相鄰元素來對數組進行排序。計劃如下：

解決步驟：

關鍵觀察：該操作允許我們僅在相鄰元素具有相同數量的設定位數時交換它們。這限制了具有不同設定位數的元素之間的交換。
計畫：
- 以二進位表示中設定的位數對元素進行分組。
- 單獨對每個群組進行排序，因為在一個群組內，元素可以透過交換來重新排列。
- 將每組排序後，將排序後的群組重新合併在一起。
- 檢查這個合併陣列是否已排序。如果是，則可以使用允許的操作對陣列進行排序。
步驟：
- 統計每個號碼中的設定位數以及具有相同設定位數的組別號碼。
- 對每個組別進行單獨排序。
- 從這些已排序的群組重建數組並驗證結果是否已排序。

讓我們用 PHP 實作這個解：3011。判斷數組是否可以排序

<?php
/**
 * Helper function to count set bits in a number
 *
 * @param $n
 * @return int
 */
function countSetBits($n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param Integer[] $nums
 * @return Boolean
 */
function canSortArray($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$nums1 = [8, 4, 2, 30, 15];
$nums2 = [1, 2, 3, 4, 5];
$nums3 = [3, 16, 8, 4, 2];
$nums4 = [75, 34, 30];

echo canBeSorted($nums1) ? 'true' : 'false'; // Expected output: true
echo "\n";
echo canBeSorted($nums2) ? 'true' : 'false'; // Expected output: true
echo "\n";
echo canBeSorted($nums3) ? 'true' : 'false'; // Expected output: false
echo "\n";
echo canBeSorted($nums4) ? 'true' : 'false'; // Expected output: false
?>

登入後複製

解釋：

countSetBits 函數：使用位元運算計算數字中設定的位數。
將元素分組：bitGroups 是一個關聯數組，其中每個鍵代表設定的位數，每個值都是具有那麼多設定位的數字數組。
排序與重建:
- 我們迭代 nums 以設定的位數將元素分組。
- 我們對每個組別進行獨立排序。
- 然後，我們透過按其原始順序插入每個已排序的群組元素來重建數組。
- 最後，我們檢查重建的陣列是否按非降序排序。如果是，則傳回true；否則，傳回 false。
最終比較：將重建的陣列與完全排序版本的 nums 進行比較。如果匹配，則傳回true；否則，傳回 false。