leetcode 排序相关题目总结
目录
Leetcode 21:合并两个有序链表
题目描述
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
解题思路
相当于归并排序中的merge操作，只不过对象换成了链表。
代码
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode res = new ListNode(-1);
ListNode head = res;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
head.next = l1;
head = head.next;
l1 = l1.next;
}
else{
head.next = l2;
head = head.next;
l2 = l2.next;
}
}
while(l1 != null){
head.next = l1;
head = l1;
l1 = l1.next;
}
while(l2 != null){
head.next = l2;
head = l2;
l2 = l2.next;
}
return res.next;
}
}
Leetcode 912: 排序数组
题目描述
给定一个整数数组 nums，将该数组升序排列。
示例 1：
输入：[5,2,3,1] 输出：[1,2,3,5] 示例 2：
输入：[5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
解题思路
这题是标准的数组排序题，也可以看作给各种排序算法的性能测试。在我提交的各种算法中，快排的性能最好。
代码
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums);
return nums;
}
private void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private void quickSort(int[] arr, int start, int end) {
if (start >= end) return;
int k = partition(arr, start, end);
quickSort(arr, start, k - 1);
quickSort(arr, k + 1, end);
}
private int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
Leetcode 378 :有序矩阵中第K小的元素
题目描述
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。 请注意，它是排序后的第k小元素，而不是第k个元素。
示例:
matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8,
返回 13。 说明: 你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。
解题思路
首先想到的是topK算法，只需要先二位矩阵展成一维数组即可。代码如下：
class Solution {
private void swap(int[] arr, int a, int b){
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
private int partition(int[] arr, int lo, int hi){
int count = lo, j = hi;
int pivot = arr[hi];
for(int i = lo; i < hi; i++){
if(arr[i] < pivot){
swap(arr, i , count);
count++;
}
}
swap(arr, count, hi);
return count;
}
private int select(int[] arr, int k){
int lo = 0, hi = arr.length -1;
while(lo < hi){
int j = partition(arr, lo, hi);
if(j < k){
lo = j + 1;
}
else if( j > k ){
hi = j -1;
}
else{
return arr[k];
}
}
return arr[k];
}
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int[] arr = new int[n * n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
arr[i * n + j] = matrix[i][j];
}
}
int res = 0;
res = select(arr, k - 1);
return res;
}
}
topk问题还可以用堆来解决, Java中的优先队列是基于 堆来实现的，默认是自然顺序，也就是从小到大的顺序，由于Java的priorityQueue只能通过peek(),poll()方法来取值，所以我们需要维护一个length - k+ 1的堆（比如要求9个元素中第8小的元素，也可以看作是9个元素中第2（9 - 8 + 1）大的元素）。
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int size = matrix.length;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i = 0; i < size; i++){
for(int j = 0; j < size; j++){
pq.add(matrix[i][j]);
if(pq.size() > size*size - k + 1) pq.poll();
}
}
return pq.peek();
}
}
Leetcode 148：排序链表
题目描述
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3 输出: 1->2->3->4 示例 2:
输入: -1->5->3->4->0 输出: -1->0->3->4->5
解题思路
1：比较直观的想法是将链表转化为数组，再排序，再重新构造链表
class Solution {
public ListNode sortList(ListNode head) {
List<Integer> arr = new ArrayList<>();
ListNode tmp = head;
while(tmp!= null){
arr.add(tmp.val);
tmp = tmp.next;
}
Collections.sort(arr);
tmp = head;
int idx = 0;
while(tmp != null){
tmp.val = arr.get(idx++);
tmp = tmp.next;
}
return head;
}
}
2：当然也可以实现基于链表的快速排序和归并排序。由于快排会用到大量的swap，而归并排序只是相邻元素间的copy,所以归并排序会更简单实现一点,效率也会更好。merge操作可以参考leetcode 21;
代码
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode mid = slow.next;
slow.next = null;
return mergeTwoLists(sortList(head),sortList(mid));
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode res = new ListNode(-1);
ListNode head = res;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
head.next = l1;
head = head.next;
l1 = l1.next;
}
else{
head.next = l2;
head = head.next;
l2 = l2.next;
}
}
while(l1 != null){
head.next = l1;
head = l1;
l1 = l1.next;
}
while(l2 != null){
head.next = l2;
head = l2;
l2 = l2.next;
}
return res.next;
}
}
Leetcode 88 :合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 示例:
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
解题思路
数组的merge操作
代码
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] aux = nums1.clone();
int i = 0, j = 0;
int idx = 0;
while(i < m && j < n){
if(aux[i] < nums2[j]){
nums1[idx] = aux[i];
i++;
}
else{
nums1[idx] = nums2[j];
j++;
}
idx++;
}
while(i < m){
nums1[idx] = aux[i];
idx++;
i++;
}
while( j < n){
nums1[idx] = nums2[j];
idx++;
j++;
}
}
}
Leetcode 280:摆动排序
题目描述
给你一个无序的数组 nums, 将该数字 原地 重排后使得 nums[0] <= nums[1] >= nums[2] <= nums[3]…。
示例:
输入: nums = [3,5,2,1,6,4] 输出: 一个可能的解答是 [3,5,1,6,2,4]
题目思路：
- 先排序，然后从第二个元素开始，每两个元素交换一下位置。
class Solution {
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
for(int i = 1; i < nums.length - 1; i+= 2){
swap(nums, i , i+ 1);
}
}
private void swap(int[] arr, int a, int b){
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
- 第二种方法就像想我们能不能一步步的将数组按摆动的顺序排好？摆动的顺序用一个表达式来表示就是：当i为偶数时，nums[i] <= nums[i + 1];当i 为奇数时，nums[i]>= nums[i +1];如果实际顺序是相反的，通过一次交换就可以达到目的，并且不会和已排好序的部分冲突。
class Solution {
public void wiggleSort(int[] nums) {
for(int i = 0; i < nums.length - 1; i++){
if((i % 2 == 1 && nums[i] < nums[i + 1])|| (i % 2 == 0 && nums[i]> nums[i+ 1])){
swap(nums, i, i + 1);
}
}
}
private void swap(int[] arr, int a, int b){
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
Leetcode 324: 摆动排序 II
题目描述
给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。
示例 1:
输入: nums = [1, 5, 1, 1, 6, 4] 输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6] 示例 2:
输入: nums = [1, 3, 2, 2, 3, 1] 输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]
解题思路
相比于leetcode280 ,这题的要求更为严苛，没有了等于。所以之前的方法是不行了，不过我们还是可以先采用先排序再构造的思路。可以先将数组折半，然后再将后半段插入到前半段中。但这样是通不过[4，5， 5， 6]这个测试案例的。所以我们需要做出调整，将后半段倒着插入到倒着的前半段中，这样就可以了。
参考答案
class Solution {
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
int[] aux = nums.clone();
int n = nums.length;
int j = (n-1)/2, k = n - 1;
for(int i = 0; i< n ; i++){
if(i % 2 == 0){
nums[i] = aux[j];
j--;
}
else{
nums[i] = aux[k];
k--;
}
}
}
}
- 上述算法的时间复杂度为O(nlogn),进阶的要求是时间复杂度为O(n),这个怎样做到呢？肯定是不能用排序了，但是我们又要保证交叉的顺序，topK算法正好可以达到要求。我们只需要用topk算法先将数组按小于median , 等于median,大于median,后续的算法就和上面一样了。
参考答案
class Solution {
private int quickSelect(int[] arr, int k){
int lo = 0, hi = arr.length -1;
while(lo <= hi){
int j = partition(arr, lo, hi);
if( j == k ) return arr[j];
if( j < k){
lo = j + 1;
}
else{
hi = j - 1;
}
}
return -1;
}
private int partition(int[] arr, int lo, int hi){
int count = lo;
int pivot = arr[hi];
for(int i = lo; i < hi; i++){
if(arr[i] < pivot){
swap(arr, count, i);
count++;
}
}
swap(arr, count , hi);
return count;
}
public void wiggleSort(int[] nums) {
int n = nums.length;
int median = quickSelect(nums,n/2 );
int[] aux =new int[n];
int left = 0, right = n - 1;
for(int i = 0 ; i < n; i++){
if(nums[i] < median){
aux[left] = nums[i];
left++;
}
else if(nums[i] > median) {
aux[right] = nums[i];
right--;
}
}
for(int i = left ; i <= right; i++){
aux[i] = median;
}
left = (n- 1)/2;
right = n - 1;
for (int i = 0; i < n; i++) {
if ( i % 2 == 0) {
nums[i] = aux[left];
left--;
} else {
nums[i] = aux[right];
right--;
}
}
}
private void swap(int[] arr, int a, int b){
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
如果需要使空间复杂度降到O(1),需要用到坐标映射。另外这个O(n) 的算法在leetcode上实际还没有O(nlogn)的算法快。
Leetcode 1122 :数组的相对排序
题目描述
给你两个数组，arr1 和 arr2，
arr2 中的元素各不相同 arr2 中的每个元素都出现在 arr1 中 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] 输出：[2,2,2,1,4,3,3,9,6,7,19]
提示：
arr1.length, arr2.length <= 1000 0 <= arr1[i], arr2[i] <= 1000 arr2 中的元素 arr2[i] 各不相同 arr2 中的每个元素 arr2[i] 都出现在 arr1 中
解题思路
可以用一个map<value, count>将arr1排序，由于arr1中的值的范围比较小，可以直接用一个数值代替map.先排arr2中的数，边排边从map中去掉。再排剩下的元素。
参考答案
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] cnt = new int[1001];
for(int num : arr1){
cnt[num]++;
}
int idx = 0;
for(int num : arr2){
while(cnt[num] > 0){
arr1[idx++] = num;
cnt[num]--;
}
}
for(int i= 0; i < 1001; i++){
while(cnt[i] > 0){
arr1[idx++] = i;
cnt[i]--;
}
}
return arr1;
}
}
Leetcode 147:对链表进行插入排序
题目描述：
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。 重复直到所有输入数据插入完为止。
解题思路
模仿数组的InsertSort,所要注意的是在head之前插入的问题和ListNode的next调整的顺序。
参考答案
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode curr = head;
while(curr != null&& curr.next != null){
ListNode tmp = curr.next;
while(tmp != null && tmp.val < curr.val){
curr.next = tmp.next;
insert(dummyHead, tmp);
tmp = curr.next;
}
curr= curr.next;
}
return dummyHead.next;
}
private void insert(ListNode dummyHead, ListNode tmp){
ListNode pre = dummyHead;
while(pre.next.val <= tmp.val){
pre = pre.next;
}
tmp.next = pre.next;
pre.next = tmp;
}
}