网站建设部署与发布,如何做教育网站,多语种网站,工程装修设计公司算法练习-排序(二) 文章目录算法练习-排序(二)1 合并排序的数组1.1 题目1.2 题解2 有效的字母异位词2.1 题目2.2 题解3 判断能否形成等差数列3.1 题目3.2 题解4 合并区间4.1 题目3.2 题解5 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面5.1 题目5.2 题解6 颜色分类6.1 题目6.…算法练习-排序(二) 文章目录算法练习-排序(二)1 合并排序的数组1.1 题目1.2 题解2 有效的字母异位词2.1 题目2.2 题解3 判断能否形成等差数列3.1 题目3.2 题解4 合并区间4.1 题目3.2 题解5 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面5.1 题目5.2 题解6 颜色分类6.1 题目6.2 题解7 最小k个数7.1 题目7.2 题解8 排序链表8.1 题目8.2 题解8.2.1 递归解法8.2.2 非递归解法9 剑指 Offer 51. 数组中的逆序对(hard)9.1 题目9.2 题解9.2.1 暴力(超时)9.2.2 逆序度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 Comparatorint[]() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});Listint[] 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;}//[q1, 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][q1, 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;}
}
