算法练习-排序(二)

1 合并排序的数组

链接：https://leetcode.cn/problems/sorted-merge-lcci

1.1 题目

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例:

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3

输出: [1,2,2,3,5,6]
说明:

A.length == n + m

1.2 题解

class Solution {public void merge(int[] A, int m, int[] B, int n) {int k = m + n - 1;int i = m - 1;int j = n - 1;while (i >= 0 && j >= 0) {if (A[i] >= B[j]) {A[k--] = A[i];i--;} else {A[k--] = B[j];j--;}}while (i >= 0) {A[k--] = A[i--];}while (j >= 0) {A[k--] = B[j--];}}
}

2 有效的字母异位词

链接：https://leetcode.cn/problems/valid-anagram

2.1 题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:

输入: s = “rat”, t = “car”
输出: false

提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

2.2 题解

class Solution {public boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}char[] str1 = s.toCharArray();char[] str2 = t.toCharArray();Arrays.sort(str1);Arrays.sort(str2);for (int i = 0; i < str1.length; i++) {if (str1[i] != str2[i]) {return false;}}return true;}
}

3 判断能否形成等差数列

链接：https://leetcode.cn/problems/can-make-arithmetic-progression-from-sequence

3.1 题目

给你一个数字数组 arr 。

如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。

如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。

示例 1：

输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
示例 2：

输入：arr = [1,2,4]
输出：false
解释：无法通过重新排序得到等差数列。

提示：

2 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6

3.2 题解

class Solution {public boolean canMakeArithmeticProgression(int[] arr) {Arrays.sort(arr);int diff = arr[1] - arr[0];for (int i = 2; i < arr.length; i++) {if (arr[i] - arr[i - 1] != diff) {return false;}}return true;}
}

4 合并区间

链接：https://leetcode.cn/problems/merge-intervals

4.1 题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

3.2 题解

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});List<int[]> result = new ArrayList<>();int curLeft = intervals[0][0];int curRight = intervals[0][1];for (int i = 1; i < intervals.length; ++i) {if (intervals[i][0] <= curRight) {if (intervals[i][1] > curRight) {curRight = intervals[i][1];}} else {result.add(new int[]{curLeft, curRight});curLeft = intervals[i][0];curRight = intervals[i][1];}}result.add(new int[]{curLeft, curRight});return result.toArray(new int[result.size()][]);}
}

5 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

链接：https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof

5.1 题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。

提示：

0 <= nums.length <= 50000
0 <= nums[i] <= 10000

5.2 题解

class Solution {public int[] exchange(int[] nums) {int i = 0;int j = nums.length - 1;while (i < j) {if (nums[i] % 2 == 1) {i++;continue;}if (nums[j] % 2 == 0) {j--;continue;}int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;i++;j--;}return nums;}
}

6 颜色分类

链接：https://leetcode.cn/problems/sort-colors

6.1 题目

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

6.2 题解

class Solution {public void sortColors(int[] nums) {int p = 0;int q = nums.length - 1;while (p < q) {if (nums[p] != 2) {p++;continue;}if (nums[q] == 2) {q--;continue;}swap(nums, p, q);p++;q--;}int i = 0;int j = p;if (nums[j] == 2) j--;while (i < j) {if (nums[i] == 0) {i++;continue;}if (nums[j] == 1) {j-;continue;}swap(nums, i, j);i++;j--;}}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;} 
}

7 最小k个数

链接：https://leetcode.cn/problems/smallest-k-lcci

7.1 题目

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]
提示：

0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))

7.2 题解

class Solution {int[] result;int count = 0;public int[] smallestK(int[] arr, int k) {if (k == 0 || arr.length < k) return new int[0];result = new int[k];quickSort(arr, 0 , arr.length - 1, k);return result;}private void quickSort(int[] nums, int p, int r, int k) {if (p > r) return;int q = partition(nums, p, r);if (q - p + 1 == k) {for (int i = p; i <= q; ++i) {result[count++] = nums[i];}} else if (q - p + 1 < k) {for (int i = p; i <= q; ++i) {result[count++] = nums[i];}quickSort(nums, q + 1, r, k - (q - p + 1));} else {quickSort(nums, p, q - 1, k);}}private int partition(int[] nums, int p, int r) {int i = p - 1;int j = p;while (j < r) {if (nums[j] < nums[r]) {swap(nums, j, i + 1);i++;}j++;}swap(nums, i + 1, r);return i + 1;}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}

8 排序链表

8.1 题目

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

8.2 题解

8.2.1 递归解法

class Solution {public ListNode sortList(ListNode head) {if (head == null) return null;if (head.next == null) return head;ListNode midNode = findMidNode(head);ListNode nextNode = midNode.next;midNode.next = null;ListNode leftNode = sortList(head);ListNode rightNode = sortList(nextNode);return mergeList(leftNode, rightNode);}private ListNode findMidNode(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}private ListNode mergeList(ListNode headA, ListNode headB) {ListNode newHead = new ListNode();ListNode tail = newHead;ListNode pa = headA;ListNode pb = headB;while (pa != null && pb != null) {if (pa.val <= pb.val) {tail.next = pa;tail = tail.next;pa = pa.next;} else {tail.next = pb;tail = tail.next;pb = pb.next;}}if (pa != null) tail.next = pa;if (pb != null) tail.next = pb;return newHead.next;}
}

8.2.2 非递归解法

class Solution {
public ListNode sortList(ListNode head) { int n = len(head);int step = 1;while (step < n) {ListNode newHead = new ListNode(); // 结果链表ListNode tail = newHead;ListNode p = head;while (p != null) {// [p, q]ListNode q = p;int count = 1;while (q != null && count < step) {q = q.next;count++;}if (q == null || q.next == null) {//这⼀轮合并结束了tail.next = p;break;}//[q+1, r]ListNode r = q.next;count = 1;while (r != null && count < step) {r = r.next;count++;}// 保存下⼀个step的起点ListNode tmp = null;if (r != null) {tmp = r.next;}// merge[p, q][q+1, r]ListNode[] headAndTail = merge(p, q, r);tail.next = headAndTail[0];tail = headAndTail[1];p = tmp;}head = newHead.next;step *= 2;}return head;}private int len(ListNode head) {if (head == null) return 0;int n = 1;ListNode p = head;while (p != null) {n++;p = p.next;}return n;}private ListNode[] merge(ListNode p, ListNode q, ListNode r) {ListNode newHead = new ListNode();ListNode tail = newHead;ListNode pa = p;ListNode pb = q.next;q.next = null;if (r != null) {r.next = null;}while (pa != null && pb != null) {if (pa.val <= pb.val) {tail.next = pa;tail = tail.next;pa = pa.next;} else {tail.next = pb;tail = tail.next;pb = pb.next;}}if (pa != null) {tail.next = pa;tail = q;}if (pb != null) {tail.next = pb;tail = r;}return new ListNode[]{newHead.next, tail};}
}

9 剑指 Offer 51. 数组中的逆序对(hard)

链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof

9.1 题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

9.2 题解

9.2.1 暴力(超时)

class Solution {public int reversePairs(int[] nums) {int count = 0;for (int i = 0; i < nums.length; i++) {int value = nums[i];for (int j = i + 1; j < nums.length; j++) {if (value > nums[j]) {count++;}}}return count;}
}

9.2.2 逆序度

逆序对个数=逆序度，排序的过程是不断减小逆序度的过程，在排序过程中，记录每步操作逆序度降低的个数，累加起来就能得到原始数据的逆序度

class Solution {int reverseCount = 0;public int reversePairs(int[] nums) {mergeSort(nums, 0, nums.length - 1);return reverseCount;}private void mergeSort(int[] nums, int p, int r) {if (p >= r) return;int q = (p + r) / 2;mergeSort(nums, p, q);mergeSort(nums, q + 1, r);merge(nums, p, q, r);}private int merge(int[] nums, int p, int q, int r) {int[] tmp = new int[r - p + 1];int i = p;int j = q + 1;int k = 0;while (i <= q && j <= r) {if (nums[j] < nums[i]) {reverseCount += (q - i + 1);tmp[k++] = nums[j];j++;} else {tmp[k++] = nums[i];i++;}}while (j <= r) {tmp[k++] = nums[j];j++;}while (i <= q) {tmp[k++] = nums[i];i++;}for (i = 0; i < r - p + 1; ++i) {nums[i + p] = tmp[i];}return reverseCount;}
}