Leetcode discuss: 324. Wiggle Sort II

April 25, 2022

Here is the link. 

C# | Using Sorting to find median value

April 25, 2022
Introduction
It takes me less than 30 minutes to learn a C# algorithm. I chose to take less optimal time complexity algorithm, and tried to learn a few things through the practice.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _324_wiggle_sort_II___Sorting
{
    class Program
    {
        static void Main(string[] args)
        {
            var nums = new int[] { 1, 5, 1, 1, 6, 4 };
            WiggleSort(nums);
        }

        /// <summary>
        /// study code:
        /// https://leetcode.com/problems/wiggle-sort-ii/discuss/77696/c-n(log(n))-easy-understand-solution-without-using-virtual-index-and-three-way-partition.
        /// Time complexity: O(NlogN)
        /// Space complexity: O(N)
        /// </summary>
        /// <param name="nums"></param>
        public static void WiggleSort(int[] nums)
        {
            if (nums.Length <= 1)
            {
                return;
            }

            // Sort the array, so it is easy to find median value
            Array.Sort(nums);

            // Learn C# Array.Clone() API 
            var copy = nums.Clone() as int[];

            var median = nums.Length % 2 == 0 ? (nums.Length / 2 - 1) : (nums.Length / 2);

            // refer to https://discuss.leetcode.com/topic/41464/step-by-step-explanation-of-index-mapping-in-java
            for (var i = 0; i < nums.Length; i++)
            {   // i is even - any number less than median
                // i is odd - any number is bigger than median
                nums[i] = i % 2 == 0 ? copy[median - i / 2] : copy[nums.Length - 1 - i / 2]; 
            }
        }
    }
}