力扣刷题篇——排序
力扣刷题篇——排序
目录
1287.题目描述🍔：
给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。 请你找到并返回这个整数 示例： 输入：arr = [1,2,2,6,6,6,6,7,10] 输出：6
解题思路🍖：
方法1：
- 注意看题目要求 是一个有序数组的特性
- 求出25%的出现次数number
- 遍历一遍数组
- 由于是有序数组 我们只需要判断i位置跟number+i的位置是否相等即可。
方法2：
- 首先将数组按递增顺序排列
- 定义一个变量 count用来记录相邻元素的次数
- 如果一共有n个数 只要确保count/arr.length>1/4 扫描一次就能找到那个条件的数了
代码附上🍳：
方法1：
class Solution {
public int findSpecialInteger(int[] arr) {
方法1:
int number=arr.length/4;
for(int i=0;i<arr.length;i++){
if(arr[i+number]==arr[i]){
return arr[i];
}
}
}
}方法2：
class Solution {
public int findSpecialInteger(int[] arr) {
//方法2：
int count=1;
int len=arr.length;
//count/len >1/4;
//4*count>len
Arrays.sort(arr);
for(int i=1;i<len;i++){
if(arr[i]==arr[i-1]){
++count;
if(4*count>len){
return arr[i];
}
}else{
count=1;
}
}
return arr[0];
}
}1464 题目描述🥖
给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。 请你计算并返回该式的最大值。 示例 1： 输入：nums = [3,4,5,2] 输出：12 解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。 示例 2： 输入：nums = [1,5,4,5] 输出：16 解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。 示例 3： 输入：nums = [3,7] 输出：12
解题思路：
这道题还是比较easyde~ 直接快乐sort就行
- 先sort进行升序排序
- 然后输出最后两个数的乘积就行~
代码附上：
class Solution {
public int maxProduct(int[] nums) {
Arrays.sort(nums);
int length=nums.length;
return (nums[length-1]-1)*(nums[length-2]-1);
}
}1636 题目描述📌：
给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。 请你返回排序后的数组。 示例 1： 输入：nums = [1,1,2,2,2,3] 输出：[3,1,1,2,2,2] 解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。 示例 2： 输入：nums = [2,3,1,3,2] 输出：[1,3,3,2,2] 解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。 示例 3： 输入：nums = [-1,1,-6,4,5,-6,1,4,1] 输出：[5,-1,4,4,-6,-6,1,1,1]
解题思路🎀：
使用map存放数组出现的次数，并将其按照出现次数升序排序，按照数字大小降序排序
代码附上：
class Solution {
public int[] frequencySort(int[] nums) {
Map<Integer,Integer> map=new HashMap<>();
for (int i = 0; i < nums.length; i++) {
//统计所有的单词出现的次数
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
//存放数字以及数字在数组中出现次数
List<int[]> list=new ArrayList<>();
//通过Entry 遍历Map
//将所有的数组中出现的数字以及数字出现的次数存放到数组当中
//以{数字，出现次数}形式存放
for (Map.Entry<Integer,Integer> entry:map.entrySet()){
list.add(new int[]{entry.getKey(),entry.getValue()});
}
int[][] arr=list.toArray(new int[list.size()][2]);
Arrays.sort(arr,(a,b)->{
//当两个数字出现的次数不相等时，将按照出现的次数进行升序排序
if(a[1]!=b[1]){
return a[1]-b[1];
}
//当两个数字在数组中出现的次数相同时，就比较两个数字的大小.按照数字的大小降序排序
else {
return b[0]-a[0];
}
});
//用于存放结果的数组
int[] res=new int[nums.length];
//将排过序的数组存放到结果数组当中
int index=0;
for (int i = 0; i < arr.length; i++) {
//将当前数字在数组中出现的次数将当前数字填充到新数组当中
for (int j = 0; j < arr[i][1]; j++) {
res[index++]=arr[i][0];
}
}
//返回结果组
return res;
}
}436 题目描述🎐
给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。 区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。 返回一个由每个区间 i 的 右侧区间 在 intervals 中对应下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。 示例 1： 输入：intervals = [[1,2]] 输出：[-1] 解释：集合中只有一个区间，所以输出-1。 示例 2： 输入：intervals = [[3,4],[2,3],[1,2]] 输出：[-1,0,1] 解释：对于 [3,4] ，没有满足条件的“右侧”区间。 对于 [2,3] ，区间[3,4]具有最小的“右”起点; 对于 [1,2] ，区间[2,3]具有最小的“右”起点。 示例 3： 输入：intervals = [[1,4],[2,3],[3,4]] 输出：[-1,2,-1] 解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。 对于 [2,3] ，区间 [3,4] 有最小的“右”起点。
解题思路🍜：
创建一个新数组把nums[i][0]的都赋值给left[i][0],left[i][1]用于记录nums的下标； 然后给b数组进行快排 然后利用二分去寻找每个右区间的数值在已经快排的b数组中比他<=的数，然后赋值rens数组；
代码附上🦪
class Solution {
public int[] findRightInterval(int[][] intervals) {
int length=intervals.length;
int res[]=new int[length];
int left[][]=new int[length][2];
for(int i=0;i<length;i++){
left[i][0]=intervals[i][0];//保存左界值
left[i][1]=i; //保存intervals的下标
}
Arrays.sort(left,(a,b)->a[0]-b[0]);
for(int i=0;i<length;i++){
res[i]=find(left,intervals[i][1]);
}
return res;
创建一个新数组把nums[i][0]的都赋值给b[i][0],b[i][1]用于记录nums的下标；
然后给b数组进行快排 然后利用二分去寻找每个右区间的数值在已经快排的b数组中比他<=的数，然后赋值ans数组；
}
public int find(int left[][],int target){
int n=left.length;
int l=0;
int r=n-1;
while(l<=r){
int c=l+(r-l)/2;
if(left[c][0]<target){
l=c+1; //大于left的情况
}else{
r=c-1;
}
}
return l==n?-1:left[l][1]; //不存在返回-1 否则返回 intervals的下标
}
}