Maximum Distance Between a Pair of Values
给两个递减数组, 找到最远的逆序对儿.
这题因为是排序好的, 用二叉搜索找, 注意先翻转一下, 然后再用lower_bound. 而且还要减去当前i的不被考虑的情况.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: int maxDistance(vector<int>& nums1, vector<int>& nums2) { int res = 0; int n = nums1.size(); int m = nums2.size(); reverse(nums2.begin(), nums2.end()); for(int i = 0; i < n; i++) { int f = lower_bound(nums2.begin(), nums2.end() - i, nums1[i]) - (nums2.begin());//[0, length - i] f = m - f - 1; res = max(res, f - i); } return res; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: string sortSentence(string s) { stringstream ss(s); string w; int n = 0; unordered_map<int, string> map; while(ss >> w){ map[w.back() - '0'] = w.substr(0, w.length() - 1); n++; } stringstream so; for(int i = 1; i <= n; i++){ so << map[i] << ' '; } string res = so.str(); return res.substr(0, res.length() - 1); } }; |