題目描述：
有一個整數陣列 nums ，和一個查詢陣列 requests ，其中 requests[i] = [starti, endi]，第 i 個查詢求 nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi] 的結果 ，starti 和 endi 陣列索引都是 從 0 開始 的，
你可以任意排列 nums 中的數字，請你回傳所有查詢結果之和的最大值，
由于答案可能會很大，請你將它對 1000000007 取余 后回傳，
示例 1：
輸入：nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
輸出：19
解釋：一個可行的 nums 排列為 [2,1,3,4,5]，并有如下結果：
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
總和為：8 + 3 = 11，
一個總和更大的排列為 [3,5,4,2,1]，并有如下結果：
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5 = 8
總和為： 11 + 8 = 19，這個方案是所有排列中查詢之和最大的結果，
示例 2：
輸入：nums = [1,2,3,4,5,6], requests = [[0,1]]
輸出：11
解釋：一個總和最大的排列為 [6,5,4,3,2,1] ，查詢和為 [11]，
示例 3：
輸入：nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
輸出：47
解釋：一個和最大的排列為 [4,10,5,3,2,1] ，查詢結果分別為 [19,18,10]，
提示：
n == nums.length
1 <= n <= 100000
0 <= nums[i] <= 100000
1 <= requests.length <= 100000
requests[i].length == 2
0 <= starti <= endi < n
解題思路：
首先是理解題意：
nums : 里的數字位置是可以隨便變動的 ;
requests : 存盤的是 每個 查詢陣列的首末位置資訊 （starti, endi） ;
題目求解相當于求 每個數字出現的次數與數字的乘積最大值， 即為sum（nums[i] * time） ;
為了求出最大的結果，出現次數較多的位置 值 相對較大 ；
例如： nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
1）、位置 1 出現了兩次， 所以 nums[1] = 5 ；
2）、位置0,2,3出現 一次 分別為 4,3,2 ；
難點：統計 每個位置出現的次數 ；
vector Intime： 記錄當前位置的入度；
vector Outtime： 記錄當前位置的出度；
vector Rtime ： 記錄當前位置出現的次數 ；
代碼實作：
class Solution {
public:
int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
long long ret = 0 ;
vector<int> Intime(nums.size() , 0) ;
vector<int> Outtime(nums.size() , 0) ;
vector<int> Rtime(nums.size() , 0) ;
int i , j ;
// 計算 i 位置的出度和入度資訊 ；
for (i = 0 ; i < requests.size() ; i ++)
{
Intime[requests[i][0]] ++ ;
Outtime[requests[i][1]] ++ ;
}
int innum = 0 ;
//統計 i 位置出現的次數 ；
for(i = 0 ; i < nums.size() ; i ++)
{
innum += Intime[i] ;
Rtime[i] = innum ;
innum -= Outtime[i] ;
}
//按照i位置出現的次數排序 ；
sort(Rtime.begin() , Rtime.end()) ;
// 按照 數字的大小排序
sort(nums.begin() , nums.end()) ;
//ret 即為所求的結果 為 ret += Rtime[i] * nums[i] ;
for (i = nums.size() - 1 ; i > -1 ; i --)
{
if (Rtime[i] == 0) break ;
ret += (long long) Rtime[i] * nums[i] ;
}
return ret % 1000000007 ;
}
};
時間復雜度：
空間復雜度：O(n) ；
時間復雜度：O(nlogn) ;
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/100654.html
標籤：其他
上一篇：C語言：函式指標及函式指標陣列