Skip to content

Commit 026cd32

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request #250 from Yrp1994/master
第一周作业-脑图
2 parents 98fd84f + 15fa3ce commit 026cd32

3 files changed

Lines changed: 162 additions & 10 deletions

File tree

‎Week_01/id_7/数据结构与算法及学习方法.png‎

1.25 MB
Loading

‎Week_03/id_7/LeetCode_295_7.cs‎

Lines changed: 147 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,147 @@
1+
/*
2+
* @lc app=leetcode.cn id=295 lang=csharp
3+
*
4+
* [295] 数据流的中位数
5+
*/
6+
using System.Collections.Generic;
7+
8+
// 方法1：暴力法，每插入一个数，就排序整个序列，一般排序时间复杂度为O(nlogn)，取中位数为O(1)，所以总的来说是O(nlogn)
9+
// 这里就不写了，实测提交会超时
10+
11+
// 方法2：使用插入排序，插入排序的时间复杂度为O(logn)，需要添加的n个数的话，遍历造成的时间复杂度为O(n)，所以总的来说是O(n)
12+
// public class MedianFinder1 {
13+
14+
// private List<int> m_lst;
15+
// /** initialize your data structure here. */
16+
// public MedianFinder1 () {
17+
// m_lst = new List<int> ();
18+
// }
19+
20+
// public void AddNum (int num) {
21+
// if (m_lst.Count == 0) {
22+
// m_lst.Add (num);
23+
// return;
24+
// }
25+
// m_lst.Insert (GetMedianIndex (0, m_lst.Count, num), num);
26+
// }
27+
28+
// public int GetMedianIndex (int start, int end, int num) {
29+
// if (start == end) {
30+
// return start;
31+
// }
32+
// int mid = (end - start) / 2 + start;
33+
// if (m_lst[mid] > num) {
34+
// return GetMedianIndex (start, mid, num);
35+
// } else if (m_lst[mid] < num) {
36+
// return GetMedianIndex (mid + 1, end, num);
37+
// } else {
38+
// return mid;
39+
// }
40+
// }
41+
42+
// public double FindMedian () {
43+
// if (m_lst.Count == 1) {
44+
// return m_lst[0];
45+
// }
46+
// if (m_lst.Count % 2 == 1) {
47+
// return m_lst[m_lst.Count / 2];
48+
// } else {
49+
// return (double) (m_lst[m_lst.Count / 2 - 1] + m_lst[m_lst.Count / 2]) / 2;
50+
// }
51+
// }
52+
// }
53+
54+
// 方法3：两个优先队列（自己使用sortedlist实现，效率不如二分法），一个降序，一个升序
55+
public class MedianFinder {
56+
57+
PriorityQueue pqo = new PriorityQueue (true);
58+
PriorityQueue pqi = new PriorityQueue ();
59+
60+
/** initialize your data structure here. */
61+
public MedianFinder () { }
62+
63+
public void AddNum (int num) {
64+
pqo.Enqueue (num);
65+
66+
pqi.Enqueue (pqo.Dequeue ());
67+
68+
if (pqo.Size () < pqi.Size ()) {
69+
pqo.Enqueue (pqi.Dequeue ());
70+
}
71+
}
72+
73+
public double FindMedian () {
74+
return pqo.Size () > pqi.Size () ? (double) pqo.Top () : (pqo.Top () + pqi.Top ()) * 0.5;
75+
}
76+
}
77+
78+
class DescendedDateComparer : IComparer<int> {
79+
public int Compare (int x, int y) {
80+
// use the default comparer to do the original comparison for int
81+
int ascendingResult = Comparer<int>.Default.Compare (x, y);
82+
83+
// turn the result around
84+
return 0 - ascendingResult;
85+
}
86+
}
87+
88+
public class PriorityQueue {
89+
private SortedList<int, int> m_sortedlst;
90+
private int m_nCount;
91+
92+
public PriorityQueue (bool blDescending = false) {
93+
if (blDescending) {
94+
m_sortedlst = new SortedList<int, int> (new DescendedDateComparer ());
95+
} else {
96+
m_sortedlst = new SortedList<int, int> ();
97+
}
98+
m_nCount = 0;
99+
}
100+
101+
public void Enqueue (int num) {
102+
if (m_sortedlst.ContainsKey (num)) {
103+
m_sortedlst[num]++;
104+
} else {
105+
m_sortedlst.Add (num, 1);
106+
}
107+
m_nCount++;
108+
}
109+
110+
public int Dequeue () {
111+
112+
if (m_nCount == 0) {
113+
return 0;
114+
}
115+
116+
int ans = m_sortedlst.Keys[0];
117+
118+
if (m_sortedlst.GetValueOrDefault (ans) > 1) {
119+
m_sortedlst[ans] = m_sortedlst.Values[0] - 1;
120+
} else {
121+
m_sortedlst.Remove (ans);
122+
}
123+
124+
m_nCount--;
125+
126+
return ans;
127+
}
128+
129+
public int Top () {
130+
if (m_nCount == 0) {
131+
return 0;
132+
}
133+
134+
return m_sortedlst.Keys[0];
135+
}
136+
137+
public int Size () {
138+
return m_nCount;
139+
}
140+
}
141+
142+
/**
143+
* Your MedianFinder object will be instantiated and called as such:
144+
* MedianFinder obj = new MedianFinder();
145+
* obj.AddNum(num);
146+
* double param_2 = obj.FindMedian();
147+
*/

Week_03/id_7/703.数据流中的第k大元素.cs renamed to Week_03/id_7/LeetCode_703_7.cs

Lines changed: 15 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -7,11 +7,13 @@
77

88
public class KthLargest {
99
int[] heap;
10+
// 堆中已经存储的数据个数
1011
int count;
12+
// 堆容量
1113
int capacity;
1214

1315
public KthLargest (int k, int[] nums) {
14-
heap = new int[nums.Length];
16+
heap = new int[k];
1517
capacity = k;
1618
count = 0;
1719
for (int i = 0; i < nums.Length; i++) {
@@ -21,16 +23,18 @@ public KthLargest (int k, int[] nums) {
2123

2224
public int Add (int val) {
2325
if (count < capacity) {
24-
heap[count++] = val;
25-
int i = count - 1;
26+
heap[count] = val;
27+
int i = count;
2628
while (i > 0) {
27-
if (heap[i] < heap[(i - 1) / 2]) {
29+
int nPIndex = (i - 1) / 2;
30+
if (heap[i] < heap[nPIndex]) {
2831
int temp = heap[i];
29-
heap[i] = heap[(i - 1) / 2];
30-
heap[(i - 1) / 2] = temp;
32+
heap[i] = heap[nPIndex];
33+
heap[nPIndex] = temp;
3134
}
32-
i = (i - 1) / 2;
35+
i = nPIndex;
3336
}
37+
count++;
3438
} else if (val > heap[0]) {
3539
heap[0] = val;
3640
int i = 0;
@@ -39,9 +43,10 @@ public int Add (int val) {
3943
if (i + 1 < count && heap[i] > heap[i + 1]) {
4044
i++;
4145
}
42-
if (heap[(i - 1) / 2] > heap[i]) {
43-
int temp = heap[(i - 1) / 2];
44-
heap[(i - 1) / 2] = heap[i];
46+
int nPIndex = (i - 1) / 2;
47+
if (heap[nPIndex] > heap[i]) {
48+
int temp = heap[nPIndex];
49+
heap[nPIndex] = heap[i];
4550
heap[i] = temp;
4651
}
4752
}

0 commit comments

Comments
 (0)