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) —
推荐阅读:海南卫视直播-海南卫视在线直播观看「高清」 青海卫视直播-青海卫视在线直播观看「高清」 西藏卫视直播-西藏卫视在线直播观看「高清」 青海安多卫视直播-青海安多藏语卫视直播「高清」 兵团卫视直播-兵团卫视在线直播观看「高清」 延边卫视直播-延边卫视在线直播观看「高清」 海峡卫视直播-海峡卫视在线直播观看「高清」 新疆卫视直播-新疆卫视在线直播观看「高清」 康巴卫视直播-康巴卫视在线直播观看「高清」 三沙卫视直播-三沙卫视在线直播观看「高清」
- 评论列表
-
- 添加评论