資訊專欄INFORMATION COLUMN
摘要：前言的第一題最小差值給定一個(gè)整數(shù)數(shù)組，對(duì)于每個(gè)整數(shù)，我們可以選擇任意滿足，并將加到中。返回的最大值和的最小值之間可能存在的最小差值。
前言
Weekly Contest 103的第一題最小差值I：
解題思路給定一個(gè)整數(shù)數(shù)組 A，對(duì)于每個(gè)整數(shù) A[i]，我們可以選擇任意 x 滿足 -K <= x <= K，并將 x 加到 A[i] 中。
在此過程之后，我們得到一些數(shù)組 B。
返回 B 的最大值和 B 的最小值之間可能存在的最小差值。
示例 1：
輸入：A = [1], K = 0 輸出：0 解釋：B = [1]示例 2：
輸入：A = [0,10], K = 2 輸出：6 解釋：B = [2,8]示例 3：
輸入：A = [1,3,6], K = 3 輸出：0 解釋：B = [3,3,3] 或 B = [4,4,4]提示：
1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000
這里介紹我的最終解題思路前，先要解讀一下題目的要求。
首先解讀一下題目的要求，這個(gè)題目的意思是給數(shù)組A中的每個(gè)元素A[i]都與x相加（x的取值范圍為[-K,K]，需要注意每個(gè)和A[i]的x可以不相同），這樣獲得一個(gè)數(shù)組B，然后取出B中的最大值和最小值相減獲得差值。由于B存在很多個(gè)，需要找去其中的差值最小的情況。這里補(bǔ)充一點(diǎn)題目沒有提到的，差值是要取絕對(duì)值的，也就是差值的最小值為0。
一看完這個(gè)題目的時(shí)候，我第一個(gè)解題的思路是模擬選擇x的過程，然后求出最小差值，也就是所謂的暴力破解。但是仔細(xì)想了一下，因?yàn)?b>x 滿足 -K <= x <= K，如果要模擬這個(gè)過程的話，必然會(huì)因?yàn)椴糠譁y(cè)試用例的整數(shù)數(shù)組 A長(zhǎng)度很大而出現(xiàn)執(zhí)行超時(shí)，而且暴力破解這個(gè)方法也不夠優(yōu)雅。
后面思考了一下，既然是求最大值和最小值的差值，為什么不先求出原數(shù)組A的最大值和最小值的差值range，然后再對(duì)range進(jìn)行兩次和x的求和獲得最小差值呢？需要注意這兩次求和都是對(duì)0的逼近。
實(shí)現(xiàn)代碼 public int smallestRangeI(int[] A, int K) {
int max=0;
int min=Integer.MAX_VALUE;
for(int i=0;iA[i]){
min=A[i];
}
}
int range=max-min;
int times=2;
while(times>0){
if(range>0){
if(range>K){
range-=K;
}else{
range=0;
}
}
--times;
}
return range;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77245.html
摘要：再向上取整為。第個(gè)要向上方求到的靠攏，需要加。最大值和最小值之差為。最終代碼若覺得本文章對(duì)你有用，歡迎用愛發(fā)電資助。 908. Smallest Range I 題目鏈接 908. Smallest Range I 題目分析 給定一個(gè)數(shù)組A和一個(gè)數(shù)字K，找到一個(gè)在-K和K之間的數(shù)字x并加到數(shù)組A中的每一個(gè)元素生成數(shù)組B，返回?cái)?shù)組B中最大值和最小值之差最小的值。 思路 根據(jù)題目，需要我們...
摘要：這個(gè)的長(zhǎng)度是最小可能的最大差值。注意考慮和兩個(gè)邊界值也要加進(jìn)去。 題目：Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Try to solve it in linear time/space. Return 0 if the...
摘要：向后移動(dòng)位簡(jiǎn)單選擇排序基本思想常用于取序列中最大最小的幾個(gè)數(shù)時(shí)。代碼實(shí)現(xiàn)循環(huán)次數(shù)選出最小的值和位置交換位置堆排序基本思想對(duì)簡(jiǎn)單選擇排序的優(yōu)化。 概述 常見的八大排序算法，它們之間的關(guān)系如下： showImg(https://segmentfault.com/img/remote/1460000011395738?w=880&h=671); 直接插入排序 希爾排序 簡(jiǎn)單選擇排序 堆排序...
摘要：說明你可以假設(shè)數(shù)組中所有元素都是非負(fù)整數(shù)，且數(shù)值在位有符號(hào)整數(shù)范圍內(nèi)。提示按奇偶排序數(shù)組給定一個(gè)非負(fù)整數(shù)數(shù)組，中一半整數(shù)是奇數(shù)，一半整數(shù)是偶數(shù)。對(duì)數(shù)組進(jìn)行排序，以便當(dāng)為奇數(shù)時(shí)，也是奇數(shù)當(dāng)為偶數(shù)時(shí)，也是偶數(shù)。 原博客地址：https://finget.github.io/2019... 排序 showImg(https://segmentfault.com/img/remote/146...
閱讀 3096·2023-04-25 20:43
閱讀 1730·2021-09-30 09:54
閱讀 1600·2021-09-24 09:47
閱讀 2890·2021-09-06 15:02
閱讀 3522·2021-02-22 17:09
閱讀 1245·2019-08-30 15:53
閱讀 1448·2019-08-29 17:04
閱讀 1970·2019-08-28 18:22
