π Hello, I'm Bai Chen. I'm not very able to stay up late π«οΌ But people who want to get better β. If you like this article, give it a compliment ποΌ Pay attention π Bai Chen! Your support is my biggest motivation! πͺπͺπͺ
πΉ preface
Bai Chen reviewed my C + + learning journey during this period and found many bumps and difficulties. Therefore, Bai Chen sorted out the good problems and big holes I encountered when I started learning C + + π§.
The sorting questions are divided into two categories: multiplechoice questions and programming questions.
 choice question
Bai Chen sorted out many knowledge points that are easy to make mistakes and difficult to master at the beginning, which is equivalent to a repeat of the important and difficult knowledge points. I hope you can deepen your understanding of the important and difficult knowledge points.
 Programming problem
Among them, it is mainly about C + + input and output, the use of STL (Standard Template Library), dynamic planning, data structure and other topics. The topics are not very difficult, but they are very representative and classic. They should be seen and mastered by every C + + beginner.
π‘ C + + entry must brush classic topics
πͺ 1. Multiple choice questions
π 1.1 type conversion of class
π Answer analysis:
π 1.2 number of copy construction calls
π Answer analysis:
π 1.3 friend function
π Answer analysis:
π 1.4 static data members
π Answer analysis:
π Answer analysis:
πΏ 1.5 new create object
π Answer analysis:
π§ 1.6 template format
π Answer analysis:
π₯ 1.7 empty class size
π Answer analysis:
The empty class system allocates a byte of space to represent the space occupation
π₯ 1.8 destructor
π Answer analysis:
π Answer analysis:
π³ 1.9 assignment operator
π Answer analysis:
π§ 1.10 constructor call
π Answer analysis:
π₯ 1.11 initialization list
π§1.12 const
π Answer analysis:
π1.13 delete this
π Answer analysis:
This is correct, but not recommended.
π₯1.14 c_str()
π Answer analysis:
Although in terms of content, a == b, a and b are two different objects, and the location stored in the space is also different, C_ The return value of STR is const char *, that is, the address in the space, so it cannot be equal.
So choose A.
π₯¨1.15 resize/reserve
π Answer analysis:
str.reserve(111); // Adjust the capacity to 111
str.resize(5); // Adjust the number of elements to 5
str.reserve(50); // The adjusted capacity is 50. Since the adjusted capacity is less than the existing space capacity, the capacity will not be reduced
So size=5 capacity=111
So the answer is: C
π₯―1.16 cerr
π₯ 1.17 base and derived classes
π§ 1.18 inherited object model
π¨ 2. Programming questions
π₯ 2.1 string addition
β Original title link: String addition
Simulation:
π Specific ideas:
We can simulate normal addition, starting from single bit and adding bit by bit. In the process of simulation, we should pay attention to:
 We take out that each element of the string is a character, so we can't add it directly. We must subtract '0' to get the real value of this number.
 When each bit of a number has been traversed, if another number has not been traversed, fill 0 in the high position of the number.
 If the sum of two numbers is greater than or equal to 10, carry.
 Insert a single digit obtained by this addition into the string to be returned each time.
 Finally, the returned string is reversed, so we need to reverse it.
π Code implementation:
class Solution { public: string addStrings(string num1, string num2) { int i = num1.size()  1, j = num2.size()  1; int flag = 0; string ret; // When the given number is not traversed or needs to be carried, it enters the loop while (i >= 0  j >= 0  flag != 0) { // Judge whether a number has been traversed int val1 = i >= 0 ? num1[i]  '0' : 0; int val2 = j >= 0 ? num2[j]  '0' : 0; // See if there is carry // flag == 1, carry; otherwise, no carry flag = flag == 1 ? val1 + val2 + 1 : val1 + val2; // Insert the number of digits added this time after the returned string ret += flag % 10 + '0'; flag /= 10; i; j; } // Reverse string reverse(ret.begin(), ret.end()); return ret; } };
π₯₯ 2.2 string multiplication
β Original title link: String multiplication
Method 1: analog vertical + addition
π Specific ideas:
Let's first look at how the multiplication in the example is calculated with the vertical formula:

We found that from right to left, each bit of num2 needs to be multiplied by num1, and the weight of the number obtained by multiplying num1 once needs to be multiplied by 10.

num2 each bit multiplied by num1 is a single digit * num1, so we can save the result of single digit multiplied by num1 and call it directly when using it.

After getting the string of num2 multiplied by num1, save it. Finally, like the vertical, add the results of each bit in turn to get the final answer.
π Code implementation:
class Solution { public: // Addition of reuse questions string Add(const string& num1, const string& num2) { string ret; int add = 0; int end1 = num1.size()  1, end2 = num2.size()  1; while (end1 >= 0  end2 >= 0  add != 0) { int n1 = end1 >= 0 ? num1[end1]  '0' : 0; int n2 = end2 >= 0 ? num2[end2]  '0' : 0; add = n1 + n2 + add; ret += add % 10 + '0'; add /= 10; } reverse(ret.begin(), ret.end()); return ret; } string multiply(string num1, string num2) { // When 0 appears, it returns "0" directly if (num1 == "0"  num2 == "0") return "0"; int len1 = num1.size(), len2 = num2.size(); // Save the value of 0 ~ 9 times num1 vector<string> save(10); // Save the value of num2 multiplied by num1 for each bit vector<string> ret(len2 + 1); // 0 times any number is 0 save[0] = "0"; // Save the last return value ret[len2] = "0"; // Record weight int pos = 0; // Save the value of 0 ~ 9 times num1 for (int i = 1; i < 10; ++i) { save[i] = Add(save[i  1], num1); } // Save the value of num2 multiplied by num1 for each bit for (int i = len2  1; i >= 0; i) { int val = num2[i]  '0'; ret[i] = save[val]; // Fill 0 after the string according to the weight for (int j = 0; j < pos; ++j) ret[i] += '0'; // The weight is increased by one for each number multiplied pos++; } // The whole adds up for (int i = 0; i < len2; ++i) { ret[len2] = Add(ret[len2], ret[i]); } return ret[len2]; } };
2. Optimize vertical + analog multiplication
π Specific ideas:
 First, let's discuss how many digits the result of multiplying m digits by n digits is.

From the above formula, the longest number obtained by final multiplication is m + n m+n m+n, so we can open up one in advance m + n m+n m+n length array to store this number.

Since we want to use multiplication for simulation, we can optimize our vertical multiplication
After the optimization, we can get the specific method through the vertical formula:
 The original step of multiplying one shaping at a time is disassembled into one number at a time and only one number at a time
 So you don't have to worry about overflow
 And we can add the multiplication result directly to the corresponding bit of the above array, just like the vertical type above
 After all the vertical operations are completed, the array obtained by processing is carried to ensure that each bit is a single digit.
 Then convert the array into a string and return.
π Code implementation:
class Solution { public: string multiply(string num1, string num2) { if (num1 == "0"  num2 == "0") return "0"; int m = num1.size(), n = num2.size(); vector<int> num(m + n); string ret; // Simulate every bit by every bit for (int i = n  1; i >= 0; i) { int val2 = num2[i]  '0'; for (int j = m  1; j >= 0; j) { int val1 = num1[j]  '0'; int mul = val1 * val2; // Add the multiplied result to the corresponding bit num[i + j + 1] += mul; } } // carry for (int i = m + n  1; i > 0; i) { num[i  1] += num[i] / 10; num[i] %= 10; } // Judge whether there is the highest position int i = num[0] == 0 ? 1 : 0; for (; i < m + n; ++i) { ret += num[i] + '0'; } return ret; } };
π 2.3 delete duplicates in ordered array
β Original title link: Remove duplicates from ordered arrays
Method 1: violent solution
π Code implementation:
class Solution { public: int removeDuplicates(vector<int>& nums) { vector<int>::iterator begin = nums.begin(); while (begin != nums.end()) { if (begin + 1 != nums.end() && *begin == *(begin + 1)) begin = nums.erase(begin); else begin++; } return nums.size(); } };
Method 2: fast and slow pointer
π Code implementation:
class Solution { public: int removeDuplicates(vector<int>& nums) { size_t slow = 0, fast = 0; size_t len = nums.size(); while (fast < len) { if (nums[slow] != nums[fast]) { nums[slow + 1] = nums[fast]; slow++; } fast++; } return slow + 1; } };
π 2.4 Yanghui triangle
β Original title link: Yanghui triangle
This is a very typical topic of dynamic programming, and the idea is also very simple.
π Specific ideas:
 Status: d p [ i ] [ j ] dp [ i ] [ j ] dp[i][j] is the number of positions
 Initial state: when j = = 0 β£ β£ i = = j Time οΌ d p [ i ] [ j ] = 1 When J = = 0  I = = J, DP [i] [J] = 1 When j==0 β£β£ i==j, dp[i][j]=1
 State transition equation: d p [ i ] [ j ] = d p [ i β 1 ] [ j β 1 ] + d p [ i β 1 ] [ j ] dp [i] [j] = dp [i  1] [j  1] + dp [i  1] [ j ] dp[i][j]=dp[iβ1][jβ1]+dp[iβ1][j].
π Code implementation:
class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> ret(numRows, vector<int>(1, 1)); for (int i = 0; i < numRows; ++i) { ret[i].resize(i + 1, 1); } for (int i = 2; i < numRows; ++i) { for (int j = 1; j < ret[i].size()  1; ++j) { ret[i][j] = ret[i  1][j  1] + ret[i  1][j]; } } return ret; } };
π 2.5 the number I that appears only once
β Original title link: A number that appears only once
First, we need to understand several properties of XOR operation:
 Commutative law: a β b = b β a , a β b β a = a β a β b a β b = b β a, a β b β a = a β a β b aβb=bβa,aβbβa=aβaβb
 Binding law: ( a β b ) β a = a β ( b β a ) (a β b) β a = a β (b β a) (aβb)βa=aβ(bβa)
 Any number exclusive or with 0 is itself: a β 0 = 0 β a = a a β 0 = 0 β a = a aβ0=0βa=a
 Any number exclusive or with itself is 0: a β a = 0 aβa=0 aβa=0
Secondly, the title clearly points out that only one number appears once and the other numbers appear twice. Therefore, according to the above nature, we can turn it into:
a 1 β a 1 β a 2 β a 2 β . . . β a k β a k + 1 β a k + 1 β . . . β a m β a m = 0 β a k = a k a_1 βa_1βa_2βa_2β...βa_kβa_{k+1}βa_{k+1}β...βa_mβa_m = 0βa_k=a_k a1ββa1ββa2ββa2ββ...βakββak+1ββak+1ββ...βamββamβ=0βakβ=akβ
That is, directly XOR all the numbers in a given array, and the final number is the number that appears only once.
π Code implementation:
class Solution { public: int singleNumber(vector<int>& nums) { int num = 0; for(auto i : nums) num ^= i; return num; } };
π 2.6 number II that appears only once
β Original title link: The number II that appears only once
π§¨ Traversal method: one
 There is nothing to say about this method. Direct violent sorting and traverse to select the number that appears only once.
π Code implementation:
class Solution { public: int singleNumber(vector<int>& nums) { if(nums.size() == 1) return nums[0]; sort(nums.begin(), nums.end()); int len = nums.size(); if(nums[0] != nums[1]) { return nums[0]; } if(nums[len  1] != nums[len  2]) { return nums[len  1]; } for(int i = 1; i < len  1; ++i) { if(nums[i] != nums[i  1] && nums[i] != nums[i + 1]) return nums[i]; } return 0; } };
Time complexity O ( n β l o g 2 n ) O(n*log_2n) O(n * log2 n), spatial complexity O ( 1 ) O(1) O(1) .
π§¨ Method 2: hash table
 Traverse the array, use the hash table to count the number of occurrences of the number in the array, and finally find the number that appears only once.
π Code implementation:
class Solution { public: int singleNumber(vector<int>& nums) { unordered_map<int, int> harsh; for (int e: nums) { ++harsh[e]; } int ret = 0; for (auto [num, cnt]: harsh) { if (cnt == 1) { ret = num; break; } } return ret; } };
Time complexity O ( n ) O(n) O(n), spatial complexity O ( n ) O(n) O(n) .
π§¨ Method 3: Statistics of binary digits
 Establish an array to count how many times 1 appears on each bit of the binary of all numbers.
 Because all the numbers except one appear three times, the sum of the times that each binary bit of the other numbers is 1 must be divided by 3.
 Therefore, we only need to count the bits in the binary bit that cannot be divided by 3, and the number composed of these bits is the number that only appears once.
π Code implementation:
class Solution { public: int singleNumber(vector<int>& nums) { int cnt[32] = { 0 }; int ret = 0; // Count the number of all binary numbers as 1 for (int i = 0; i < 32; ++i) { for (auto e : nums) { if ((e >> i) & 1 == 1) { cnt[i]++; } } } // The result is to wait for bits or that cannot be divided by 3 for (int i = 0; i < 32; ++i) { if ((cnt[i] % 3)) ret = 1 << i; } return ret; } };
Time complexity O ( n ) O(n) O(n), spatial complexity O ( 1 ) O(1) O(1) .
π 2.7 number III that appears only once
β Original title link: Number III that appears only once
β¨ Method 1: sorting + traversal
 Sort directly, and then traverse to select the number that appears only once.
π Code implementation:
class Solution { public: vector<int> singleNumber(vector<int>& nums) { sort(nums.begin(), nums.end()); int len = nums.size(); vector<int> ret; // Special case: judge the first element and the second element if(nums[0] != nums[1]) { ret.push_back(nums[0]); } // Special case: judge the last element and the penultimate element if(nums[len  1] != nums[len  2]) { ret.push_back(nums[len  1]); } if(ret.size() == 2) return ret; // General judgment: judge other elements in the array for(int i = 1; i < len  1; ++i) { if(nums[i] != nums[i  1] && nums[i] != nums[i + 1]) ret.push_back(nums[i]); } return ret; } };
Time complexity O ( n β l o g 2 n ) O(n*log_2n) O(n * log2 n), spatial complexity O ( 1 ) O(1) O(1) .
β¨ Method 2: hash table
 Violence hash, directly count the number of occurrences of each number, and finally select the number that appears only once.
π Code implementation:
class Solution { public: vector<int> singleNumber(vector<int>& nums) { unordered_map<int, int> freq; for (int num: nums) { ++freq[num]; } vector<int> ans; for (const auto& [num, occ]: freq) { if (occ == 1) { ans.push_back(num); } } return ans; } };
β¨ Method 3: binary XOR method
π Specific ideas:
 First, we need to understand several properties of XOR operation:
 Commutative law: a β b = b β a , a β b β a = a β a β b a β b = b β a, a β b β a = a β a β b aβb=bβa,aβbβa=aβaβb
 Binding law: ( a β b ) β a = a β ( b β a ) (a β b) β a = a β (b β a) (aβb)βa=aβ(bβa)
 Any number exclusive or with 0 is itself: a β 0 = 0 β a = a a β 0 = 0 β a = a aβ0=0βa=a
 Any number exclusive or with itself is 0: a β a = 0 aβa=0 aβa=0
Secondly, it is clearly pointed out in the title that only two figures appear once, and the other figures appear twice. Therefore, according to the above nature, we can turn them into:
a 1 β a 1 β a 2 β a 2 β . . . β a k β a k + 1 β a k + 1 . . . β a n β a n + 1 β a n + 1 β . . . β a m β a m = a k β a n a_1 βa_1βa_2βa_2β...βa_kβa_{k+1}βa_{k+1}...βa_nβa_{n+1}βa_{n+1}β...βa_mβa_m = a_kβa_n a1ββa1ββa2ββa2ββ...βakββak+1ββak+1β...βanββan+1ββan+1ββ...βamββamβ=akββanβ
Finally, we get the XOR values of two numbers that only appear once. According to the definition of XOR, the numbers on the binary bits of the two numbers are different, and the result on the different bits is 1, eg. 1000 ⊕ 1110 = 0110. We can get that the second and third bits of the two numbers are different from right to left.
 When we get the different binary bits of the target number, we can group the array according to the order. After grouping, there is only one single number left in each group.
 Select the number I twice.
π Code implementation:
class Solution { public: vector<int> singleNumber(vector<int>& nums) { int num = 0; int len = nums.size(); vector<int> ret; // XOR all numbers together for(auto e : nums) { num ^= e; } int i = 0; // Find out the binary bits of two different numbers for(i = 0; i < 32; ++i) { if((num >> i) & 1 == 1) break; } // Group according to different binary bits for XOR, and finally get two results directly int ret1 = 0, ret2 = 0; for(auto e : nums) { if((e >> i) & 1 == 1) ret1 ^= e; else ret2 ^= e; } ret.push_back(ret1); ret.push_back(ret2); return ret; } };
Time complexity O ( n ) O(n) O(n), spatial complexity O ( 1 ) O(1) O(1) .
π 2.8 letter combination of telephone number
β Original title link: Letter combination of telephone number
π Specific ideas:
This is a very classic backtracking algorithm problem, and the idea is actually very simple:
 Traverse the number string given by the topic and find the corresponding letter string according to the number.
 Add characters after the current in the order of traversed elements until the traversal is completed.
 When traversing the numeric string given by the title, save the string obtained at this time.
π Code implementation:
// Hash table for comparison static string harsh[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; class Solution { public: void Dfs(string& digits, int index, string curStr, vector<string>& ret) { // When the length of the current string is equal to digits, if the current string is not empty, insert it if(curStr.size() == digits.size()) { if(!curStr.empty()) ret.push_back(curStr); return; } // Find the number corresponding to the current digits int curInd = digits[index]  '0'; // Traverse the corresponding string in this hash table for(auto& ch: harsh[curInd]) { // Try each result. The index is the subscript of digits, and add one at a time // Each time you add the current corresponding hash table character after the current string, try all possibilities Dfs(digits, index + 1, curStr + ch, ret); } } vector<string> letterCombinations(string digits) { vector<string> ret; Dfs(digits, 0, "", ret); return ret; } };
π 2.9 maximum sum of continuous subarrays
β Original title link: Maximum sum of continuous subarrays
This problem is a classic dynamic programming problem. Some students may do it directly with greed + backtracking at the first glance, but if this problem uses greedy algorithm, in some cases, the overall optimal result will not be obtained.
π Specific ideas:
This is a classic dynamic programming problem:

Status: f ( x ) f(x) f(x)  from the continuous maximum sum of the previous section to the maximum sum of x position

State transition equation: f ( x ) = m a x ( f ( x β 1 ) + a [ x ] , a [ x ] ) f(x)=max(f(x1) + a[x], a[x]) f(x)=max(f(x − 1)+a[x],a[x])  if the sum of the continuous maximum sum of the previous segment and the current number is greater than the current number, take the sum of the continuous maximum sum of the previous segment and the current number, otherwise, take the current number (equivalent to if the maximum value of the sum of the previous continuous string and the sum of the current number are not as good as the current number, it is better to restart a continuous substring from this position, otherwise continue the previous continuous string)

Initial value: f ( 0 ) = a [ 0 ] f(0) = a[0] f(0)=a[0]  substring starting from a[0]

Result: from f ( 0 ) β f ( n β 1 ) f(0)  f(n1) Select the maximum value from f(0) − f(n − 1). Because the continuous string is uncertain, we should make a final judgment.

example: β 2 , 1 , β 3 , 4 , β 1 , 2 , 1 , β 5 2 ,1,3,4,1,2,1,5 β2,1,β3,4,β1,2,1,β5

Serial number 0 1 2 3 4 5 6 7 a [ x ] a[x] a[x] 2 1 3 4 1 2 1 5 f ( x ) f(x) f(x) 2 1 2 4 3 5 6 1
Let's summarize the idea of continuous string vividly:
It is equivalent to you have a large family. If your family's assets are very rich and your assets add up to more than your original assets (you may owe money), you choose to inherit the family property; But if your family is in a bad situation and your family owes money, you can choose to go out and work alone. Don't be implicated by the family. You start to establish a new family again. Your children and grandchildren follow your example and continue the above process.
Finally, your descendants read the genealogy to find the era of the widest instrument in their ancestors, so they compare the assets of generations to get the assets of the widest generation in their ancestors.
π Code implementation:
class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { int num = array[0], Max = array[0]; for(int i = 1; i < array.size(); ++i) { num = max(array[i] + num, array[i]); Max = num > Max ? num : Max; } return Max; } };
π₯ 2.10 minimum stack
β Original title link: Minimum stack
Since this problem requires to find the minimum value in linear time, we can exchange space for time.
π Specific ideas:
 Preset two stacks, one to store the normally entered value _ st, another dedicated storage minimum _ min.
 Stack:
 The stack value is directly stored in the_ stοΌ
 _ When the st stack is empty, it is put into the stack at the same time_ minοΌ
 When stacking later, and_ Compare the stack top elements of min, if the value in the stack is less than or equal to_ Min is the top element of the stack_ min.
 Out of stack:
 When out of the stack, if_ The stack element of st is equal to_ min, then both stacks are out of the stack;
 If_ The stack element of st is not equal to_ min stack top element, only_ st stack.
π Code implementation:
class MinStack { public: MinStack() {} void push(int val) { _st.push(val); if (_min.empty()  val <= _min.top()) { _min.push(val); } } void pop() { if (_min.top() == _st.top()) { _min.pop(); } _st.pop(); } int top() { return _st.top(); } int getMin() { return _min.top(); } private: stack<int> _st; stack<int> _min; };
π 2.11 stack push in and popup sequence
β Original title link: Push in and popup sequence of stack
The main idea of this problem is simulation.
π Specific ideas:
 Directly simulate the process of entering and leaving the stack.
 Enter the stack in sequence according to the given stack entry order. When the input element is the same as the first element of the stack exit sequence, start the stack exit, point to the next element of the stack exit sequence, and cycle this process until the top element of the stack is different from the element of the stack exit sequence or the stack is empty.
 Loop through the above process until the stack sequence is traversed.
 At this moment, if there are no elements in the stack, the given sequence of the title is correct. On the contrary, it is incorrect.
π Code implementation:
class Solution { public: bool IsPopOrder(vector<int> pushV, vector<int> popV) { stack<int> st; int i = 0, j = 0; // Loop through the following process until the stack sequence is traversed while (i < pushV.size()) { st.push(pushV[i++]); // When the top element of the stack is equal to the out of stack sequence, the out of stack starts while (!st.empty() && st.top() == popV[j]) { st.pop(); j++; } } return st.empty(); } };
π 2.12 evaluation of inverse Polish expression
β Original title link: Evaluation of inverse Polish expression
The inverse Polish expression was proposed by lukaswicz, a Polish logician. The characteristic of inverse Polish expression is that there are no parentheses and the operator is always placed after its associated operand. Therefore, the inverse Polish expression is also called suffix expression.
π Specific ideas:
The inverse Polish expression strictly follows the operation of "left to right". When calculating the value of the inverse Polish expression, use a stack to store operands, traverse the inverse Polish expression from left to right, and perform the following operations:

If an operand is encountered, the operand is put on the stack;

If an operator is encountered, the two operands will be out of the stack. The right operand will be out of the stack first, and the left operand will be out of the stack later. Use the operator to operate the two operands and put the new operand obtained by the operation into the stack.

After traversing the whole inverse Polish expression, there is only one element in the stack, which is the value of the inverse Polish expression.
The above idea comes from the official
π Code implementation:
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> st; for (const auto& str : tokens) { if (str == "+"  str == ""  str == "*"  str == "/") { int right = st.top(); st.pop(); int left = st.top(); st.pop(); switch (str[0]) { case '+': st.push(left + right); break; case '': st.push(left  right); break; case '*': st.push(left * right); break; case '/': st.push(left / right); break; } } else { st.push(stoi(str)); } } return st.top(); } };
π 2.13 the kth largest element in the array
β Original title link: The kth largest element in the array
π Method 1: sorting
Sort directly and select the kth element with a time complexity of O ( n β l o g Β n ) O(n*log~n) O(nβlogΒ n).
class Solution { public: int findKthLargest(vector<int>& nums, int k) { sort(nums.begin(), nums.end(), greater<int>()); return nums[k  1]; } };
π Method 2: heap sorting
Using heap sorting, the time complexity is O ( n + k β l o g Β n ) O(n+k*log~n) O(n+kβlogΒ n)
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> pq(nums.begin(), nums.end()); for (int i = 1; i < k; ++i) { pq.pop(); } return pq.top(); } };
π Method 3: TopK
TopK problem, directly establish a small stack of k elements, and use the solution of TopK. The time complexity is O ( n + n β l o g Β k ) O(n + n*log~k) O(n+n * log k), this is the optimal solution of this problem.
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k); for (int i = k; i < nums.size(); ++i) { if (nums[i] > pq.top()) { pq.pop(); pq.push(nums[i]); } } return pq.top(); } };
Students who have not learned about piles can read this article—— [data structure] full parsing of heap , which explains the heap sorting and TopK problems in detail.
β Postscript
Bai Chen wrote this article to help more C + + entrylevel learners master the syntax of C + + faster, and can use C + + in practice. I hope you can gain something from this article.
If this article helps you, please support Bai Chen. Your support is the greatest encouragement to Bai Chen π.
If there is something wrong with the analysis, please correct it. I will modify it as soon as possible. Thank you for your tolerance.
If you like this series, please support it π!
If this article helps you, please give me a thumb π And little stars β Support Bai Chen! If you like Bai Chen's [brush question diary] series, you might as well pay attention to it π Bai Chen, in order to see the latest updates!!!
I'm Bai Chen who can't stay up late. I'll see you in the next article.