Mündəricat
Problem bəyanat :
Ən kiçik diapazon II Leetcode həlli – Sizə tam ədədlər massivi verilir nömrə və tam ədəd k.
Hər bir indeks üçün i hara 0 <= i < ədədlər.uzunluq, dəyişdirin nums [i] ya olmaq ədəd[i] + k or ədəd[i] – k.
The hesab of nömrə -dəki maksimum və minimum elementlər arasındakı fərqdir nömrə.
Qayıtmaq minimum hesab of nömrə hər bir indeksdəki dəyərləri dəyişdirdikdən sonra.
Misal:
Məsələn 1
Input: nums = [1], k = 0 Output: 0 Explanation: The score is max(nums) - min(nums) = 1 - 1 = 0.
Məsələn 2
Input: nums = [0,10], k = 2 Output: 6 Explanation: Change nums to be [2, 8]. The score is max(nums) - min(nums) = 8 - 2 = 6.
Məsələn 3
Input: nums = [1,3,6], k = 3 Output: 3 Explanation: Change nums to be [4, 6, 3]. The score is max(nums) - min(nums) = 6 - 3 = 3.
Məhdudiyyətlər:
Müşahidə:
- Qoy edək maksimum massivdəki element be max və minimum element dəqiqə.
- Əgər massiv dəyərlərini dəyişdirməyə icazə verilməsəydi, o zaman tamamilə aydındır ki maksimum fərq (maxdiff) olacaq
maxdiff= max-min.
-
- Amma bizim məqsəd bu fərqi minimuma endirməkdir Bəs bunu hansı yolla edə bilərik? Aydındır ki, hər ikisi tərəfindən hündürlükləri k ilə artırmaq və ya azaltmaq. Gəlin hamısını sınayaq mümkün birləşmələr artan və azalan min və maks.
- Həm maksimum, həm də minimum hündürlüklərin artırılması:
Yeni maksimum = maks + k
Yeni minimum = min + k
Yeni maxdiff = ( maks + k ) - ( min + k ) = maksimum – min
Bu, orijinal maxdiff ilə eynidir. Beləliklə, hər iki dəyərin artırılması orijinal cavabı dəyişmir və buna görə də istifadəsi yoxdur.
- Həm maksimum, həm də minimum hündürlüklərin azaldılması:
Yeni maksimum = maksimum – k
Yeni minimum =min – k
Yeni maxdiff = ( maksimum – k) - ( min – k) = maksimum – min
Bu, orijinal maxdiff ilə eynidir. Beləliklə, hər iki dəyərin azalması orijinal cavabı dəyişmir və buna görə də istifadəsi yoxdur.
- Maksimum artım və minimum hündürlüklərin azalması:
Yeni maksimum = maks + k
Yeni minimum = min – k
Yeni maxdiff = ( maks + k ) - ( min – k) = maksimum – min + 2*k
Orijinal fərqimizi artırdıq 2*k. Bu, cavabımızı pisləşdirəcək və buna görə də belədir istifadəsi yoxdur.
- Maksimum azaldılması və minimum hündürlüyün artırılması:
Yeni maksimum = maksimum – k
Yeni minimum = min + k
Yeni maxdiff = ( maksimum – k ) - ( min + k ) = maksimum-min – 2*k
Orijinal fərqimizi azaltdıq 2*k. Bu olacaq cavabımızı təkmilləşdirin.
Beləliklə, cavabımızı yaxşılaşdırmaq üçün massivin maksimum dəyərini azaltmalı və minimum dəyəri artırmalıyıq.
Alqoritm:
- Başlanğıcda cür massivi, beləliklə biz arasında ən yaxşı fərqlərdən birini tapa bilək dəqiqə dəyəri və max verilmiş massivdəki dəyər. (yəni, yuxarıdakı kodda ans dəyişəni).
- İndi, massivdə təkrarlayın və cərəyanı artırın i'th k ilə qiymət verin və ilə müqayisə edin ədəd[n-1]-k, tapmaq üçün yeni maks.
- Azaldın i + 1 ilə k və tapmaq yeni min müqayisə etməklə ədəd[0]+k.
- Nəhayət, qayıt il olanları max-min min fərqi.
Ən kiçik diapazon üçün kod II
Java Kodu
// we need to find min Score (Maximum - Minimum )
// for minmising we can decrease the maximum one or else we can increase the minimum
// first find the min and max of nums
class Solution {
public int smallestRangeII(int[] nums, int k) {
int n = nums.length;
Arrays.sort(nums);
int maxE=nums[n-1];
int minE=nums[0];
int ans=maxE-minE;
for (int i = 0; i < n - 1; ++i) {
int currMax = Math.max(nums[n-1] - k, nums[i] + k);
int currMin = Math.min(nums[0] + k, nums[i+1] - k);
ans = Math.min(ans, currMax - currMin);
}
return ans;
}
}
C++ kodu
class Solution {
public:
int smallestRangeII(vector<int>& nums, int k) {
int n=nums.size();
sort(nums.begin(),nums.end());
int maxE=nums[n-1];
int minE=nums[0];
int ans=maxE-minE;
for(int i=0;i<n-1;i++){
int currMax=max(maxE-k,nums[i]+k);
int currMin=min(minE+k,nums[i+1]-k);
ans=min(currMax-currMin,ans);
}
return ans;
}
};
Ən kiçik diapazon II Leetcode Həlli üçün Mürəkkəblik Təhlili
Zamanın mürəkkəbliyi
, Harada N uzunluğu nömrə.
Kosmik Mürəkkəblik
O(1).
