วิธีจัดเรียง 0 และ 1 ในอาร์เรย์โดยไม่ใช้พื้นที่เพิ่มเติมด้วย C#

ใช้ two pointers low และ high เราจะใช้ low pointer ที่จุดเริ่มต้น และ high pointer จะชี้ที่ปลายของอาร์เรย์ที่กำหนด

ถ้า array[low] = 0 แล้วไม่ต้องสลับ

ถ้า array[low] = 1 แล้วต้องสลับ ลด high pointer ลง 1

Time complexity - O(N)

ตัวอย่าง

using System;

namespace ConsoleApplication
{
    public class Arrays
    {
        public void SwapZerosOnes(int[] arr)
        {
            int low = 0;
            int high = arr.Length - 1;
            while (low < high)
            {
                if (arr[low] == 1)
                {
                    Swap(arr, low, high);
                    high--;
                }
                else
                {
                    low++;
                }
            }
        }

        private void Swap(int[] arr, int pos1, int pos2)
        {
            int temp = arr[pos1];
            arr[pos1] = arr[pos2];
            arr[pos2] = temp;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Arrays a = new Arrays();
            int[] arr1 = { 0, 1, 1, 0, 1, 1 };
            a.SwapZerosOnes(arr1);
            for (int i = 0; i < arr1.Length; i++)
            {
                Console.WriteLine(arr1[i]);
            }
        }
    }
}

ผลลัพธ์

0 0 1 1 1 1