学校网站建设的意见,电话销售的10个小技巧,上海各区的网站有哪些公司,大连中小网站建设公司给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。
请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。
分析#xff1a;这是个排序题#xff0c;只要排好序#xff0c;一切迎刃而解。我决定把排序…给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
分析这是个排序题只要排好序一切迎刃而解。我决定把排序算法多试几个把答案都写下来。从小到大排序
1.冒泡排序 两两比较如果前面的较小就交换顺序
class Solution {public int findKthLargest(int[] nums, int k) {for(int i 0;inums.length;i){for(int j 0;j nums.length-i-1;j){//第i次后最后面i1个元素已经排好了只需要在遍历num.s-i1次if(nums[j]nums[j1]){//相邻元素比较int temp nums[j];nums[j] nums[j1];nums[j1] temp;}}}return nums[nums.length-k];}
}时间复杂度是O(n^2) 2.选择排序 每趟从剩下的nums.length-i中选择最小的插入到第i1个位置
class Solution {public int findKthLargest(int[] nums, int k) {for(int i 0;inums.length;i){int p i;//p一直会寻找最小的元素下标for(int j i1;jnums.length;j){if(nums[j]nums[p]){p j;}}if(p i){//也可以直接交换continue;}else{int temp nums[i];nums[i] nums[p];nums[p] temp;}}return nums[nums.length-k];}
}时间复杂度O(n^2)
3.插入算法 插入排序是把一个记录插入到已排序的有序序列中使整个序列在插入该记录后仍然有序。插入排序中较简单的一种方法是直接插入排序其插入位置的确定方法是将待插入的记录与有序区中的各记录自右向左依次比较其关键字值的大小。
class Solution {public int findKthLargest(int[] nums, int k) {int j 0;for(int i 1;inums.length;i){//从第二个数据开始一个数据没有可比性int temp nums[i];//取出要插入的数据j i-1;//确定要比较元素的最右边位置while(j0tempnums[j]){nums[j1] nums[j];//数据右移j--;//移向左边一个未比较的数}nums[j1] temp;//在确定的位置插入nums[i]}return nums[nums.length-k];}
}时间复杂度O(n^2)
