# 前言
提示：排序相关题解
一、三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
public class Solution {
public static List<List<Integer>> threeSum(int[] nums){
List<List<Integer>> ans = new ArrayList<>();
if(nums==null||nums.length<3){
return ans;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if(nums[i]>0){
break;
}
if(i>0&&nums[i]==nums[i-1]){
continue;
}
int l=i+1;
int r=nums.length-1;
while (l<r){
int sum = nums[i]+nums[l]+nums[r];
if(sum==0){
ans.add(Arrays.asList(nums[i],nums[l],nums[r]));
while(l<r && nums[l]==nums[l+1]) l++;
while(l<r && nums[r]==nums[r-1]) r--;
l++;
r--;
}else if(sum<0){
l++;
}else if(sum>0){
r--;
}
}
}
return ans;
}
}
二、字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词指字母相同，但排列不同的字符串。
public class Solution {
public List<List<String>> groupAnagrams(String[] strs){
HashMap<String,List<String>> map = new HashMap();
for (String str : strs) {
char[] s = str.toCharArray();
Arrays.sort(s);
String k =new String(s);
List<String> a = map.getOrDefault(k,new ArrayList<String>());
a.add(str);
map.put(k,a);
}
return new ArrayList<List<String>>(map.values());
}
}
三、合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
public class Solution {
public int[][] merge(int[][] intervals){
if(intervals.length==0){
return new int[0][2];
}
Arrays.sort(intervals,new Comparator<int[]>(){
public int compare(int[]intervals1,int[] intervals2){
return intervals1[0]-intervals2[0];
}
});
List<int[]> a = new ArrayList<>();
for (int i = 0; i < intervals.length; i++) {
int l = intervals[i][0];
int r = intervals[i][1];
if(a.size()==0||a.get(a.size()-1)[1]<l){
a.add(new int[]{l,r});
}else {
a.get(a.size()-1)[1]=Math.max(a.get(a.size()-1)[1],r);
}
}
return a.toArray(new int[a.size()][]);
}
}
四、颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
public class Solution {
public void sortColors(int[] nums){
int l =0;
int r =nums.length-1;
int i =0;
while (i<=r){
if(nums[i]==0){
exc(nums,i,l);
l++;
i++;
}else if(nums[i]==1){
i++;
}else {
exc(nums,i,r);
r--;
}
}
}
private void exc(int[] nums,int l,int r){
int tmp =nums[l];
nums[l]=nums[r];
nums[r]=tmp;
}
}
五、合并两个有序数组
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
class Solution {
public void merge(int[] nums1,int m,int[] nums2,int n) {
int a= 0;
int b =0;
int[] num = new int[m+n];
int i =0;
while (a<m||b<n){
if(a==m){
i=nums2[b];
b++;
}else if(b==n){
i=nums1[a];
a++;
}else if(nums1[a]<nums2[b]){
i=nums1[a];
a++;
}else {
i=nums2[b];
b++;
}
num[a+b-1]=i;
}
for (int j = 0;j<m+n;j++){
nums1[j]=num[j];
}
}
}
六、排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回排序后的链表 。
class Solution {
public ListNode sortList(ListNode head) {
if(head==null||head.next==null){
return head;
}
ListNode fast=head.next;
ListNode slow = head;
while (fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
ListNode tmp = slow.next;
slow.next=null;
ListNode left =sortList(head);
ListNode right = sortList(tmp);
ListNode cur = new ListNode(0);
ListNode pre =cur;
while (left!=null&&right!=null){
if(left.val<right.val){
cur.next=left;
left=left.next;
cur=cur.next;
}else {
cur.next=right;
right=right.next;
cur=cur.next;
}
}
cur.next= left==null? right:left;
return pre.next;
}
}
七、多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ? n/2 ? 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
八、最大数
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
class Solution {
public String largestNumber(int[] nums) {
String[] snum = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
snum[i] = String.valueOf(nums[i]);
}
Arrays.sort(snum,(a,b)->{
return (b+a).compareTo(a+b);
});
if(snum[0].equals("0")){
return "0";
}
StringBuilder s = new StringBuilder();
for (int i = 0; i < nums.length; i++) {
s.append(snum[i]);
}
return s.toString();
}
}
九、数组中的第k各最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
class Solution {
public int findKthLargest(int[] nums, int k){
qSort(nums,0,nums.length-1);
return nums[nums.length-k];
}
private void qSort(int[] nums,int left,int right){
if(left>right){
return;
}
int i =left;
int j =right;
int tmp =nums[left];
while (i!=j){
while (i<j&&nums[j]>=tmp){
j--;
}
while (i<j&&nums[i]<=tmp){
i++;
}
if(i<j){
int t =nums[i];
nums[i] =nums[j];
nums[j]=t;
}
}
nums[left] = nums[i];
nums[i]=tmp;
qSort(nums,left,i-1);
qSort(nums,i+1,right);
}
}
十、存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false
class Solution {
public boolean containsDuplicate(int[] nums) {
int n =nums.length;
HashMap<Integer,Integer> map =new HashMap<>();
for(int i =0;i<n;i++){
if(!map.containsKey(nums[i])){
map.put(nums[i],1);
}else{
return true;
}
}
return false;
}
}
十一、有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
class Solution {
public boolean isAnagram(String s, String t) {
char[] a= s.toCharArray();
char[] b =t.toCharArray();
Arrays.sort(a);
Arrays.sort(b);
if(Arrays.equals(a,b)){
return true;
}
return false;
}
}
十二、丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
for(int i =0;i<n;i++){
if(nums[i]!=i){
return i;
}
}
return n;
}
}
十三、摆动排序
给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。
你可以假设所有输入数组都可以得到满足题目要求的结果。
class Solution {
public void wiggleSort(int[] nums) {
int[] button =new int[5001];
for(int num:nums){
button[num]++;
}
int small;
int big;
if((nums.length%2)==1){
small = nums.length-1;
big =nums.length-2;
}else{
small = nums.length-2;
big =nums.length-1;
}
int j =5000;
for(int i =1;i<=big;i=i+2){
while(button[j]==0){j--;}
nums[i]=j;
button[j]--;
}
for (int i =0;i<=small;i=i+2){
while(button[j]==0){j--;}
nums[i]=j;
button[j]--;
}
}
}
十四、前K个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
public class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int num : nums) {
if(map.containsKey(num)){
int n =map.get(num);
map.put(num,n++);
}else {
map.put(num,1);
}
}
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return map.get(o1)-map.get(o2);
}
});
for (Integer integer : map.keySet()) {
if(pq.size()<k){
pq.add(integer);
}else if(map.get(integer)>map.get(pq.peek())){
pq.remove();
pq.add(integer);
}
}
int[] tmp =new int[k];
int i =0;
while (!pq.isEmpty()){
tmp[i++]=pq.remove();
}
return tmp;
}
}
十五、两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
int m =nums1.length;
int n =nums2.length;
if(m>n) {
return intersect(nums2,nums1);
}
int[] tmp = new int[n];
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
if(map.containsKey(nums1[i])){
int nn =map.get(nums1[i]);
map.put(nums1[i],n++);
}else {
map.put(nums1[i],1);
}
}
int j = 0;
for (int i : nums2) {
if(map.containsKey(i)&&map.get(i)>0){
tmp[j] =i;
j++;
map.put(i,map.get(i)-1);
}
}
return Arrays.copyOfRange(tmp,0,j);
}
}
十六、有序矩阵中第K个小的元素
给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int m =matrix.length;
int n =matrix[0].length;
int[] a = new int[m*n];
int ii =0;
for(int i = 0;i<m;i++){
for(int j=0;j<n;j++){
a[ii++]= matrix[i][j];
}
}
Arrays.sort(a);
return a[k-1];
}
}
|