74. 数组中的第K个最大元素（堆/215）
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
假设：
1 <= k <= nums.length <= $(10)^5$；
$(-10)^4$ <= nums[i] <= $(10)^4$。
示例：输入: [3,2,1,5,6,4], k = 2；输出: 5。
【分析】
解法1：使用堆，空间换时间，时间复杂度O(nlogk)。
堆（heap,数据结构）：堆是一种特殊的完全二叉树。C#中没有具体的接口或类可用于堆，可以自己建一个，使用数组来存储，为堆结构写一个上浮和下沉的方法使堆可以排序为大顶堆或小顶堆。
最大堆（大顶堆）：每个节点的值都大于或等于其子节点的值。
最小堆（小顶堆）：每个节点的值都小于或等于其子节点的值。
解法2：快速选择算法，时间复杂度O(n)。
快速选择算法是快速排序的一个变种，它用于在未排序的数组中找到第 k 大（或第 k 小）的元素。
分区函数式为了找到枢纽元素在数组中的最终位置，也是快排的核心算法。
每次调整后只取随机枢纽元素的一侧进行递归再排序。
就取第K个最大元素这个需求而言，不需要把整个数组排序，只要找到第K个最大元素的正确位置即可。
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| public class Solution{
public int FindKthLargest1(int[] nums, int k){
}
public int FindKthLargest2(int[] nums, int k){
QuickSort(nums,0,nums.Length-1,k);
return nums[nums.Length-k];
}
public void QuickSort(int[] nums, int left, int right, int k){
if(left<right){
int pviot=Partition(nums,left,right);
if(pviot==nums.Length-k){
return;
}
if(pviot>nums.Length-k){
QickSort(nums,left,pviot-1,k);
}else{
QickSort(nums,pviot+1,right,k);
}
}
}
public int Partition(int[] nums, int left, int right){
Swap(nums,left,(left+right)/2);
int pviotNum=nums[left];
while(left<right){
while(left<right && nums[right]>=pviotNum){
right--;
}
nums[left]=nums[right];
while(left<right && nums[left]<=pviotNum){
left++;
}
nums[right]=nums[left];
}
nums[left]=pviotNum;
return left;
}
public void Swap(int[] nums, int a, int b){
if(nums[a]!=nums[b]){
int temp=nums[a];
nums[a]=nums[b];
nums[b]=temp;
}
}
}
|
77. 买股票的最佳时机（贪心算法/121）
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
假设：
1 <= prices.length <= $(10)^5$；
0 <= prices[i] <= $(10)^4$。
示例：输入：[7,1,5,3,6,4]；输出：5。
【分析】
找到整数数组中的两个元素，使得后一元素减去前一元素的差最大。
时间复杂度O(n)，空间复杂度O(1)。
1
2
3
4
5
6
7
8
9
10
11
| public class Solution{
public int MaxProfit(int[] prices){
int minPrice=prices[0];
int maxProfit=0;
foreach(int price in prices){
minPrice=Math.Min(minPrice,price);
maxProfit=Math.Max(maxProfit,price-minPrice);
}
return maxProfit;
}
}
|
