Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/03/02 00:20)推噓3(3推 0噓 1→)

留言4則, 4人參與討論串255/719 (看更多)

912. Sort an Array 給你一個陣列請排序他，時間複雜度最多O(nlogn)，空間複雜度盡可能少。 Example: Input: nums = [5,2,3,1] Output: [1,2,3,5] Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5). 思路： 1.因為題目需求時間複雜度O(nlogn)，所以只能用高等排序來求解，其中HeapSort和 QuickSort空間用的最少所以挑這兩個其一來實現即可。 Java Code： ------------------------------------ class Solution { public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); return nums; } private static void quickSort(int[] array, int left, int right) { if (left >= right) { return; } int pivot = array[(left + right) / 2]; int index = partition(array, left, right, pivot); quickSort(array, left, index - 1); quickSort(array, index, right); } private static int partition(int[] array, int left, int right, int pivot) { while (left <= right) { while (array[left] < pivot) { left++; } while (array[right] > pivot) { right--; } if (left <= right) { swap(array, left, right); left++; right--; } } return left; } private static void swap(int[] array, int left, int right) { int temp = array[left]; array[left] = array[right]; array[right] = temp; } } ------------------------------------ -- https://i.imgur.com/tdaniED.jpg