LeetCode 912. 排序数组
2023-09-11 14:19:00 时间
思路
手撕快速排序。
class Solution {
public int[] sortArray(int[] nums) {
// 手撕快速排序
int left = 0, right = nums.length-1;
quickSort(nums, left, right);
return nums;
}
public void quickSort(int[] nums, int left, int right) {
if(left >= right) return;
// 随机选一个数当主元,randIndex表示该随机主元的下标
int randIndex = new Random().nextInt(right-left+1)+left;
swap(nums, left, randIndex);
int pivot = nums[left];
int i = left, j = right;
while(i != j) {
while(i < j && nums[j] >= pivot) j--;
while(i < j && nums[i] <= pivot) i++;
swap(nums, i, j);
}
swap(nums, left, i);
quickSort(nums, left, i-1);
quickSort(nums, i+1, right);
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
相关文章
- Leetcode: Lowest Common Ancestor of a Binary Search Tree
- Leetcode: Longest Palindromic Substring && Summary: Palindrome
- leetcode Valid Palindrome C++&python 题解
- LeetCode高频题:如何不用int转字符数组,实现int类型数字x的第L位和R位数字交换
- 后缀数组的应用:[Leetcode]1062. 最长重复子串(困难)
- JS Leetcode 81. 搜索旋转排序数组 II 题解,补救二分法的可行性
- JS leetcode 有序数组的平方 题解分析,灵活运用Math.pow与Math.abs方法
- [LeetCode]剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
- [LeetCode]1486. 数组异或操作
- 【Java数据结构与算法】LeetCode 0206. 反转链表的三种Java实现方法
- 178、【数组/动态规划】leetcode ——392. 判断子序列:双指针+动态规划(C++版本)
- 175、【动态规划】leetcode ——718. 最长重复子数组 (C++版本)
- 152、【动态规划】leetcode ——416. 分割等和子集:滚动数组+二维数组(C++版本)
- 105、【树与二叉树】leetcode ——530. 二叉搜索树的最小绝对差:中序遍历递归法+迭代法(C++版本)
- 【LeetCode】86. Partition List
- leetcode 218: The Skyline Problem
- 【leetcode】3: 无重复字串的最长子串(python)
- 【leetcode】26:删除有序数组中的重复项 II
- [LeetCode] 1331. Rank Transform of an Array 数组序号转换
- [LeetCode] 1328. Break a Palindrome 破坏回文串
- [LeetCode] 1237. Find Positive Integer Solution for a Given Equation 找出给定方程的正整数解
- [LeetCode] 1043. Partition Array for Maximum Sum 分隔数组以得到最大和
- [LeetCode] 1122. Relative Sort Array 数组的相对排序
- [LeetCode] 1002. Find Common Characters 寻找相同字符
- [LeetCode] 932. Beautiful Array 漂亮数组
- [LeetCode] 912. Sort an Array 数组排序
- [LeetCode] 453. Minimum Moves to Equal Array Elements 最少移动次数使数组元素相等
- [LeetCode] 154. Find Minimum in Rotated Sorted Array II 寻找旋转有序数组的最小值之二
- leetcode 34. Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位置(中等)