LeetCode-CSharp/Solution/0977.Squares-of-a-sort-array/0977-Squares-of-a-sort-array.cs at main · FakeStandard/LeetCode-CSharp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
using System;
using System.Collections.Generic;
using System.Text;

namespace Solution._0977.Squares_of_a_sort_array
{
    public class _0977_Squares_of_a_sort_array
    {
        public int[] SortedSquares(int[] nums)
        {
            for (int i = 0; i < nums.Length; i++)
                nums[i] *= nums[i];

            //QuickSort(ref nums, 0, nums.Length - 1);

            // Faster than Quick Sort.
            //Array.Sort(nums);

            QuickSort(ref nums, 0, nums.Length - 1);

            return nums;
        }

        private void QuickSort(ref int[] data, int left, int right)
        {
            if (left >= right)
                return;

            int i = Partition(data, left, right);
            QuickSort(ref data, left, i - 1);
            QuickSort(ref data, i + 1, right);
        }

        private int Partition(int[] data, int left, int right)
        {
            int i = left;
            int pivot = data[right];

            for (int j = left; j < right; j++)
            {
                if (data[j] < pivot)
                {
                    Swap(ref data, i, j);
                    i++;
                }
            }

            Swap(ref data, i, right);

            return i;
        }

        private void Swap(ref int[] nums, int i, int j)
        {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }

        //private void QuickSort(ref int[] data, int left, int right)
        //{
        //    if (left > right)
        //        return;

        //    int pivot = data[left];
        //    int i = left;
        //    int j = right;
        //    int temp = 0;

        //    while (i != j)
        //    {
        //        while (data[j] >= pivot && i < j)
        //            j--;

        //        while (data[i] <= pivot && i < j)
        //            i++;

        //        if (i < j)
        //        {
        //            temp = data[i];
        //            data[i] = data[j];
        //            data[j] = temp;
        //        }
        //    }

        //    data[left] = data[i];
        //    data[i] = pivot;

        //    QuickSort(ref data, left, i - 1);
        //    QuickSort(ref data, i + 1, right);
        //}
    }
}