原题
给定一个整数数组 nums，将该数组升序排列。
示例 1:
输入： [5,2,3,1] 输出： [1,2,3,5]
示例 2:
输入： [5,1,1,2,0,0] 输出： [0,0,1,1,2,5]
提示：
1 <= A.length <= 10000-50000 <= A[i] <= 50000
解法
思想
经典排序问题，解法见十大排序算法与Java实现
代码
计数排序：
class Solution {
public int[] sortArray(int[] nums) {
int[] occur = new int[100001];
for(int num:nums){
occur[num+50000]++;
}
int index = 0;
for(int i = 0;i<100001;i++){
if(occur[i]!=0){
for(int n = 0 ; n < occur[i];n++){
nums[index] = i-50000;
index++;
}
}
}
return nums;
}
}
快速排序，这里每次选取中轴元素都是选取的第一个元素：
class Solution {
public int[] sortArray(int[] nums) {
return quickSort(nums,0,nums.length-1);
}
private int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
//获取中轴元素所处的位置
int mid = partition(arr, left, right);
//进行分割
arr = quickSort(arr, left, mid - 1);
arr = quickSort(arr, mid + 1, right);
}
return arr;
}
private int partition(int[] arr, int left, int right) {
//选取中轴元素
int pivot = arr[left];
int i = left + 1;
int j = right;
while (true) {
// 向右找到第一个小于等于 pivot 的元素位置
while (i <= j && arr[i] <= pivot) i++;
// 向左找到第一个大于等于 pivot 的元素位置
while(i <= j && arr[j] >= pivot ) j--;
if(i >= j)
break;
//交换两个元素的位置，使得左边的元素不大于pivot,右边的不小于pivot
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[left] = arr[j];
// 使中轴元素处于有序的位置
arr[j] = pivot;
return j;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode912-%e6%8e%92%e5%ba%8f%e6%95%b0%e7%bb%84/
相关推荐
-
leetcode134-加油站
原题 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[...
-
leetcode779-第K个语法符号
原题 在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。 给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始） 例子： 输入: N...
-
leetcode131-分割回文串
原题 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], ...
-
leetcode141-环形链表
原题 给定一个链表，判断链表中是否有环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没...
-
leetcode1248-统计「优美子数组」
原题 给你一个整数数组 nums 和一个整数 k。 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。 请返回这个数组中「优美子数组」的数目。 ...
-
leetcode98-验证二叉搜索树
原题 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和...
-
leetcode11-盛最多水的容器
原题 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i,...
-
leetcode155-最小栈
原题 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() ...
-
程序员面试金典01.06-字符串压缩
原题（来源Leetcode） 字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字...
