324.ウォブリング順序II(JS実装)

6237 ワード

1テーマ
無秩序な配列numsを与え、nums[0]nums[2]リンク:https://leetcode-cn.com/problems/wiggle-sort-ii
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];
  }
};