Leetcode 1471. The k Strongest Values in an Array(3种方法)

Leetcode 1471. The k Strongest Values in an Array(3种方法)

Leetcode 1471. The k Strongest Values in an Array

题目链接： The k Strongest Values in an Array

难度：Medium

题目大意：

输入一组数，如果元素a与中位数之差的绝对值比b与中位数之差的绝对值大，则认为a大于b,如果相等则比较数值，数值较大的数大。返回题目要求的前k个最大的数。

思路：

思路1（数组排序）：

先对数组按数值进行排序，求出中位数。然后对数组按题目的要求进行排序，返回排序后数组的前k个元素。

思路2 （优先队列）：

先对数组按数值进行排序，求出中位数。用优先队列来存储题目要求的最大的k个数。

思路3（双指针）：

先对数组按数值进行排序，求出中位数。与中位数差值绝对值最大的元素要么在最左边要么在最右边，进行比较即可得出，按照这个方法找出最大的k个数。

代码

思路1：

class Solution {//通过数组排序求解public int[] getStrongest(int[] arr, int k) {int n=arr.length;int m=(n-1)/2;Arrays.sort(arr);int mid=arr[m];Integer A[]=new Integer[n];for(int i=0;i<n;i++){A[i]=new Integer(arr[i]);}Arrays.sort(A,new Comparator<Integer>(){public int compare(Integer a,Integer b){if(Math.abs(a-mid)!=Math.abs(b-mid)){return Math.abs(b-mid)-Math.abs(a-mid);}else{return b-a;}} });for(int i=0;i<k;i++){arr[i]=A[i].intValue();}pyOfRange(arr,0,k);}
}

思路2：

class Solution {//通过优先队列求解public int[] getStrongest(int[] arr, int k) {int len=arr.length;int m=(len-1)/2;Arrays.sort(arr);int mid=arr[m];Queue<Integer> pq=new PriorityQueue<Integer>(new Comparator<Integer>(){public int compare(Integer a,Integer b){if(Math.abs(a-mid)!=Math.abs(b-mid)){return Math.abs(a-mid)-Math.abs(b-mid);}else{return a-b;}//注意优先级与题目要求的相反}});for(int n:arr){pq.offer(n);if(pq.size()>k){pq.poll();}}int[] res=new int[k];for(int i=k-1;i>=0;i--){res[i]=pq.poll();}return res; }
}

思路3：

class Solution {//用双指针求解public int[] getStrongest(int[] arr, int k) {int len=arr.length;Arrays.sort(arr);int mid=arr[(len-1)/2];int[] res=new int[k];int p=0;int i=0,j=len-1;while(p<k){if(arr[j]-mid>=mid-arr[i]){res[p++]=arr[j--];}else{res[p++]=arr[i++];}}return res;}
}