908-最小差值I

KunMinX 發布于2019-08-19 11:14 / 1874人閱讀

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

前言

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

給定一個整數數組 A，對于每個整數 A[i]，我們可以選擇任意 x 滿足 -K <= x <= K，并將 x 加到 A[i] 中。
在此過程之后，我們得到一些數組 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

解題思路

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

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

一看完這個題目的時候，我第一個解題的思路是模擬選擇x的過程，然后求出最小差值，也就是所謂的暴力破解。但是仔細想了一下，因為x 滿足 -K <= x <= K，如果要模擬這個過程的話，必然會因為部分測試用例的整數數組 A長度很大而出現執行超時，而且暴力破解這個方法也不夠優雅。

后面思考了一下，既然是求最大值和最小值的差值，為什么不先求出原數組A的最大值和最小值的差值range，然后再對range進行兩次和x的求和獲得最小差值呢？需要注意這兩次求和都是對0的逼近。

實現代碼

    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;
    }

云服務器 GPU云服務器日期差值差值 python求差值 java 計算日差值

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77245.html

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

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

ethernet 2019-07-01 12:38 評論0 收藏0
164. Maximum Gap

摘要：這個的長度是最小可能的最大差值。注意考慮和兩個邊界值也要加進去。題目：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 2019-08-14 14:09 評論0 收藏0
八大排序算法Java實現

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

Coly 2019-08-15 11:57 評論0 收藏0
JavaScript數據結構與算法-Sort-(leetcode原題)

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

Hanks10100 2019-08-23 18:08 評論0 收藏0