网站维护做啥的,郑州大学网页设计与网站建设,网站毕业设计论文模板,织梦cms怎样做网站本题中#xff0c;我们的题目求的是差值的最小值#xff0c;我们考虑一个因素#xff0c;当前题目中给出的数组是没有排序过的#xff0c;那么想要求的差值#xff0c;是不是要两两配对进行判断差值最小值。这里我们就很费时间了#xff0c;
O(N^2)的时间复杂度#xf…
本题中我们的题目求的是差值的最小值我们考虑一个因素当前题目中给出的数组是没有排序过的那么想要求的差值是不是要两两配对进行判断差值最小值。这里我们就很费时间了
O(N^2)的时间复杂度那么我们怎么办呢排序吗不太行排完序的话后面查询就很麻烦了不可取此时我们在注意一下数据数字只有100那么这个就是这题的关键点之一了只有100个数。那么我们再来考虑差值的最小值差值的最小值是不是只有相邻的两数才行如果不相邻的话那么必然不可能是差值最小值。所以这是第二个关键点贪心贪的是相邻的数。
那么我们怎么知道区间之内的数有哪些呢前缀和但是前缀和我们只知道数有多少个了那怎么知道该区间有没有这个数这个我们也是可以通过前缀和知道的因为我们统计的前缀和是区间内的数字的个数那么我们就可以知道这个个数了利用前缀和性质相减一下就知道个数了。
那么我们利用前缀和求出个数利用贪心的思想我们就可以解决这道题目了
class Solution {
public:int ss[111000][110];vectorint minDifference(vectorint nums, vectorvectorint queries) {memset(ss,0,sizeof(ss));ss[1][nums[0]];int n nums.size();for(int i 2;i n;i){memcpy(ss[i],ss[i - 1],sizeof(ss[i]));ss[i][nums[i - 1]];}vectorint ans;for(autoq:queries){int prev -1;int left q[0];int right q[1];int res 0x3f3f3f3f;for(int i 1;i 100;i){if(abs(ss[right 1][i] - ss[left][i]) 0){if(prev ! -1){res min(res,i - prev);}prev i;}}if(res ! 0x3f3f3f3f) ans.push_back(res);else ans.push_back(-1);}return ans;}
};
