Replace Elements with Greatest Element on Right Side using C++ s
- 时间:2020-09-12 10:17:13
- 分类:网络文摘
- 阅读:104 次
Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1. After doing so, return the array.
Example 1:
Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]Constraints:
1 <= arr.length <= 10^4
1 <= arr[i] <= 10^5Hints:
Loop through the array starting from the end.
Keep the maximum value seen so far.
Using Additional Maximum Array
Let’s allocate another array storing the maximum values from the right. Then, it is a straightforward solution:
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: vector<int> replaceElements(vector<int>& arr) { if (arr.empty()) return {}; vector<int> vmax(arr.size()); for (int i = arr.size() - 2; i >= 0; -- i) { vmax[i] = max(vmax[i + 1], arr[i + 1]); } vmax[arr.size() - 1] = -1; return vmax; } }; |
class Solution { public: vector<int> replaceElements(vector<int>& arr) { if (arr.empty()) return {}; vector<int> vmax(arr.size()); for (int i = arr.size() - 2; i >= 0; -- i) { vmax[i] = max(vmax[i + 1], arr[i + 1]); } vmax[arr.size() - 1] = -1; return vmax; } };
Time complexity is O(N) as we are iterating the entire array.
Modifying the existing array
We can modify the existing array along the way, then we need a variable to save the current value in the array then update the current maximum, and store it in the next iteration.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: vector<int> replaceElements(vector<int>& arr) { if (arr.empty()) return {}; int mx = 0; for (int i = arr.size() - 1; i >= 0; -- i) { int a = arr[i]; arr[i] = mx; mx = max(mx, a); } arr[arr.size() - 1] = -1; return arr; } }; |
class Solution { public: vector<int> replaceElements(vector<int>& arr) { if (arr.empty()) return {}; int mx = 0; for (int i = arr.size() - 1; i >= 0; -- i) { int a = arr[i]; arr[i] = mx; mx = max(mx, a); } arr[arr.size() - 1] = -1; return arr; } };
O(N) time and O(1) constant space.
Using std::exchange() in C++
The C++ std::exchange() offers a cleaner implementation of above.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: vector<int> replaceElements(vector<int>& arr) { if (arr.empty()) return {}; int mx = 0; for (int i = arr.size() - 1; i >= 0; -- i) { mx = max(mx, exchange(arr[i], mx)); } arr[arr.size() - 1] = -1; return arr; } }; |
class Solution { public: vector<int> replaceElements(vector<int>& arr) { if (arr.empty()) return {}; int mx = 0; for (int i = arr.size() - 1; i >= 0; -- i) { mx = max(mx, exchange(arr[i], mx)); } arr[arr.size() - 1] = -1; return arr; } };
As you can see, the std::exchange(a, b) will be equivalent to the following:
1 2 3 4 5 6 | template <class T> T exchange(T a, T b) { T x = a; a = b; return x; } |
template <class T> T exchange(T a, T b) { T x = a; a = b; return x; }
Unlike the std::swap(), the second paramter won’t be modified. The original value of first parameter i.e. a will be returned.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:1 不是质数的原因 钟声的问题 越减越多的问题 数图形的问题 一笔画问题 我们家的清明习俗 悲惨童年|小学作文 北京春节的习俗 快乐艺术节 我爱秋天的凄凉
- 评论列表
-
- 添加评论