数组的排序

数组中的第k个最大元素及出现的次数

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
1
2

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
1
2

提示：

• 1 <= k <= nums.length <= 104
• -104 <= nums[i] <= 104
  通过次数542,143提交次数838,220

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

数组中的第k个最大元素-快速排序

需要找的是数组排序后的第k个最大的元素，先对数组进行排序，再找到第k个元素。
排序中比较快的算法是快排、归并、堆排序。

选择快速排序，快排速度快，但是容易受初始状态影响，所以我们就随机选择一个基准值。
比基准值大的放左边，比基准值小的放右边(从大到小排序)，找到基准值的位置之后，与k比较
大于k说明第k个元素在左边，小于k说明第k个元素在右边，就可以排除一半的答案
剩下的一半结果又重新选择基准值，重复上述步骤，直到找到第k大的元素。

需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。假设[5,5,4,3,2,1]k=2，那么我们找的是5而不是4

function findKthLargest(nums: number[], k: number): number {
    quickSort(nums,0,nums.length-1,k);
    return nums[k-1];
};

function quickSort(nums:number[],left:number,right:number,k:number):void{
   if(left<right){
        let index = findIndex(nums,left,right);//找到了基准值的位置
        if(index==k-1) return;
        if(index>k-1) quickSort(nums,left,index-1,k); 
        else quickSort(nums,index+1,right,k);
    }

}

function findIndex(nums:number [],left:number,right:number):number{
    let randomIndex = Math.floor(Math.random()*(right-left+1)+left);
    let privot = nums[randomIndex]; //基准值
    [ nums[randomIndex],nums[left]] = [nums[left], nums[randomIndex]]; //将left的位置存放基准值
    while(left<right){//从大到小排序
        while(left<right && nums[right]<=privot) right--;
        nums[left] = nums[right];
        while(left<right && nums[left]>=privot) left++;
        nums[right] = nums[left];
    }//等于right说明已经找到了
    nums[left] = privot;

    return left;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

如果第K大的数说的是不同的元素，那么可以先排序之后去重，找到第K大的元素

如何寻找第K大的出现了几次？

排完序之后遍历数组，与第K大的进行比较

function findKthLargestCount(nums, k){
    quickSort(nums,0,nums.length-1,k); //先从大到小排序，后比较
    let num = nums[k-1];
	let count = 0;
	for(let i of arr){
		if(i==num)count++;
		else if(i<num)break;
	}
	console.log(count);
};
1
2
3
4
5
6
7
8
9
10

还有一种思路是:找到目标元素第一次出现的位置，以及比目标元素小的下一个元素第一次出现的位置(可以通过去重数组后,目标元素的下一个索引元素)，相减即可。

数组正态分布排序

问题描述

var arr = [1,2,1,3,3,2,4,6,3]，通过处理将其变为正态分布的形式： [1,2,3,3,6,4,3,2,1]。

正态分布数组的特性

1. 中间最大，两边递减
2. 以最大值为中心点，左右两部分和尽可能相等

代码实现

思路
先对数组进行排序，将下标为偶数的放一个数组A的结尾(要保证依次递增)，下标为奇数的放入另外一个数组B的开头(要保证依次递减)
为了保证左右两侧相等或者大致相等，每当数组A和数组B长度一致时，如果B的和大于A的和，就将A的最后一个和B的第一个交换

function sort(arr){
	let sortArr = arr.sort((a,b)=>a-b); //从大到小排
	let tempLeft=[],tempRight=[];
	let i=0;
	let tempLeftSum=0;
	let tempRightSum=0;
	for(;i<arr.length;++i){
		let cur = sortArr[i];
		if(i%2==0){
			tempLeft.push(cur);
			tempLeftSum+=cur;
		}
		else{
			tempRight.unshift(cur);
			tempRightSum+=cur;
		}
		if(i>1){ //从下标1开始就可以比较了
			if(tempLeft.length==tempRight.length && tempRightSum>tempLeftSum){
				//左边最后一个和右边第一个进行交换
				[tempRight[0],tempLeft[tempRight.length-1]]= [tempLeft[tempRight.length-1],tempRight[0]] 
			}
		}
	}
	return tempLeft.concat(tempRight);
}
//测试代码
let arr =[1,2,1,3,3,2,4,6,3];
console.log(sort(arr))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28