324.ウォブリング順序II(JS実装)
6237 ワード
1テーマ
無秩序な配列numsを与え、nums[0]nums[2]リンク:https://leetcode-cn.com/problems/wiggle-sort-ii
2考え方
この問題をすると、まず配列を並べ替えて、配列を二つの部分に分けて、順番に新しい配列を作ります.問題解にはO(n)のアルゴリズムがあります.まず快速選択法を使って、配列の中央値を見つけて、それから中央値以下の数を左側に置いて、中央値より大きいものを右側に置くと、二つの部分になります.
3コード
無秩序な配列numsを与え、nums[0]
2考え方
この問題をすると、まず配列を並べ替えて、配列を二つの部分に分けて、順番に新しい配列を作ります.問題解にはO(n)のアルゴリズムがあります.まず快速選択法を使って、配列の中央値を見つけて、それから中央値以下の数を左側に置いて、中央値より大きいものを右側に置くと、二つの部分になります.
3コード
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var wiggleSort = function(nums) {
nums.sort((a,b) => a-b);
let mid = nums.length % 2 === 0 ? Math.floor(nums.length / 2) : Math.floor(nums.length / 2) + 1;
const res = [];
let low = mid - 1;
let high = nums.length - 1;
while (low >= 0 && high >= mid) {
res.push(nums[low--]);
res.push(nums[high--]);
}
if (low >= 0) res.push(nums[low--]); //
if (high >= mid) res.push(nums[high--]); //
for (let i=0; i<res.length;i++) {
nums[i] = res[i];
}
};