亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

908-最小差值I

KunMinX / 1941人閱讀

摘要：前言的第一題最小差值給定一個整數(shù)數(shù)組，對于每個整數(shù)，我們可以選擇任意滿足，并將加到中。返回的最大值和的最小值之間可能存在的最小差值。

前言

Weekly Contest 103的第一題最小差值I：

給定一個整數(shù)數(shù)組 A，對于每個整數(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
解題思路

這里介紹我的最終解題思路前，先要解讀一下題目的要求。

首先解讀一下題目的要求，這個題目的意思是給數(shù)組A中的每個元素A[i]都與x相加（x的取值范圍為[-K,K]，需要注意每個和A[i]的x可以不相同），這樣獲得一個數(shù)組B，然后取出B中的最大值和最小值相減獲得差值。由于B存在很多個，需要找去其中的差值最小的情況。這里補(bǔ)充一點(diǎn)題目沒有提到的，差值是要取絕對值的，也就是差值的最小值為0。

一看完這個題目的時候，我第一個解題的思路是模擬選擇x的過程，然后求出最小差值，也就是所謂的暴力破解。但是仔細(xì)想了一下，因?yàn)?b>x 滿足 -K <= x <= K，如果要模擬這個過程的話，必然會因?yàn)椴糠譁y試用例的整數(shù)數(shù)組 A長度很大而出現(xiàn)執(zhí)行超時，而且暴力破解這個方法也不夠優(yōu)雅。

后面思考了一下，既然是求最大值和最小值的差值，為什么不先求出原數(shù)組A的最大值和最小值的差值range，然后再對range進(jìn)行兩次和x的求和獲得最小差值呢？需要注意這兩次求和都是對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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/77245.html

相關(guān)文章

  • Leetcode PHP題解--D18 908. Smallest Range I

    摘要：再向上取整為。第個要向上方求到的靠攏，需要加。最大值和最小值之差為。最終代碼若覺得本文章對你有用，歡迎用愛發(fā)電資助。 908. Smallest Range I 題目鏈接 908. Smallest Range I 題目分析 給定一個數(shù)組A和一個數(shù)字K，找到一個在-K和K之間的數(shù)字x并加到數(shù)組A中的每一個元素生成數(shù)組B，返回數(shù)組B中最大值和最小值之差最小的值。 思路 根據(jù)題目，需要我們...

    ethernet 評論0 收藏0

  • 164. Maximum Gap

    摘要：這個的長度是最小可能的最大差值。注意考慮和兩個邊界值也要加進(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...

    EddieChan 評論0 收藏0

  • 八大排序算法Java實(shí)現(xiàn)

    摘要：向后移動位簡單選擇排序基本思想常用于取序列中最大最小的幾個數(shù)時。代碼實(shí)現(xiàn)循環(huán)次數(shù)選出最小的值和位置交換位置堆排序基本思想對簡單選擇排序的優(yōu)化。 概述 常見的八大排序算法，它們之間的關(guān)系如下： showImg(https://segmentfault.com/img/remote/1460000011395738?w=880&h=671); 直接插入排序 希爾排序 簡單選擇排序 堆排序...

    Coly 評論0 收藏0

  • JavaScript數(shù)據(jù)結(jié)構(gòu)與算法-Sort-(leetcode原題)

    摘要：說明你可以假設(shè)數(shù)組中所有元素都是非負(fù)整數(shù)，且數(shù)值在位有符號整數(shù)范圍內(nèi)。提示按奇偶排序數(shù)組給定一個非負(fù)整數(shù)數(shù)組，中一半整數(shù)是奇數(shù)，一半整數(shù)是偶數(shù)。對數(shù)組進(jìn)行排序，以便當(dāng)為奇數(shù)時，也是奇數(shù)當(dāng)為偶數(shù)時，也是偶數(shù)。 原博客地址：https://finget.github.io/2019... 排序 showImg(https://segmentfault.com/img/remote/146...

    Hanks10100 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<