908. Smallest Range I (最小差值 I)

更新於 發佈於 閱讀時間約 1 分鐘


英文版點我中文版點我


↑看個小廣告,支持好內容↑



讀懂這段在表達啥,這題就算解掉一半了

讀懂這段在表達啥,這題就算解掉一半了

陣列中的每項都有一次調整的機會,可以被任意改成 nums[i]-k~nums[i]+k 之間的整數,而我們的目標是:盡可能縮小陣列的全距 (最大值-最小值)。


似乎很直觀,就把小的數字變大一點、大的數字變小一點就好了對吧?

// 成功的案例
nums=[1,9], k=2: 1397,全距=4

// 失敗的案例
nums=[5,7], k=3: 5874,全距=4
(顯然不對,這比調整前的差距還大)


事實上,直接把 5 改成 7,兩數就相同了,故正確答案應該是 0;即便我們在陣列加入很多很多 6,他們照樣可以被改成 7,並不影響結果。綜上,我們得到兩個結論:


  • 最小範圍確實是由 [max, min] 所決定。
  • 差值不會為負,當 max-min-2*k<0,答案必定為 0。


[備註] 這題因為文字敘述收到許多負評,但我認為它是刻意為之的,如何在有限時間內消化提取線索解題,也是邏輯與閱讀素養的一大考驗。話說回來,把蕪雜的需求化約進程式設計,這本身就是開發實務的縮影哪~ (茶


  • 本題分類標籤:ArrayMath
  • 本題正解率=69.3%

❤️ 若內容對你實用,歡迎追蹤本專題,或小額贊助支持~
⭐ 這是我的第 13 篇刷題筆記,完整解題索引看這裡 → Here

avatar-img
54會員
59內容數
我要成為 LeetCode 王!快跟我一起踏上旅程!
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
LeetCode King 的其他內容
老是從頭重算可不是好法子,把加過的累積值存起來備用,這才符合 Prefix Sum 的精神!
三種做法所花的時間都不同,請試著一步步優化,在只跑一次迴圈下完成吧!
你聽過 "LIFO" 嗎?搞不好在解這題時你已經不知不覺用到它了喔 XD
只講得出一種做法就輸了!畫點文氏圖,幫你複習一下集合運算~
這道題你一定會解,但你知道怎麼把迴圈改寫成「迭代」嗎?這招學起來!
一串數字能夠組成等差數列嗎?有沒有不排列就能判斷的方法?
老是從頭重算可不是好法子,把加過的累積值存起來備用,這才符合 Prefix Sum 的精神!
三種做法所花的時間都不同,請試著一步步優化,在只跑一次迴圈下完成吧!
你聽過 "LIFO" 嗎?搞不好在解這題時你已經不知不覺用到它了喔 XD
只講得出一種做法就輸了!畫點文氏圖,幫你複習一下集合運算~
這道題你一定會解,但你知道怎麼把迴圈改寫成「迭代」嗎?這招學起來!
一串數字能夠組成等差數列嗎?有沒有不排列就能判斷的方法?
你可能也想看
Google News 追蹤
Thumbnail
隨著理財資訊的普及,越來越多台灣人不再將資產侷限於台股,而是將視野拓展到國際市場。特別是美國市場,其豐富的理財選擇,讓不少人開始思考將資金配置於海外市場的可能性。 然而,要參與美國市場並不只是盲目跟隨標的這麼簡單,而是需要策略和方式,尤其對新手而言,除了選股以外還會遇到語言、開戶流程、Ap
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
題目敘述 Find K-th Smallest Pair Distance 給定一個輸入陣列nums和 參數k。 請找出第k小的pair distance是多少? pair distance定義為 abs( nums[i] - nums[j]), i 不等於j 也就是任意兩陣列元素差值的絕對值
Thumbnail
題目敘述 Longest Arithmetic Subsequence of Given Difference 給定一個整數陣列nums,請找出給定公差difference的最長的等差數列的長度是多少?
Thumbnail
輸入給定一個已經從小到大排序好,而且彼此互質的整數陣列, 請問任取兩數分別當作分子、分母,第k小的分數是多少? 輸出請以 [分子,分母] 的形式回傳答案。
Thumbnail
題目敘述 給定一個非零陣列nums,請找出陣列裡面 最大的對偶數 是誰? 如果無解,請返回-1 對偶數定義: 整數k的對偶數是-k 例如: 99 和 -99互為對偶數。
Thumbnail
題目敘述 題目會給定一個二元陣列nums(也就是說,陣列元素只有0,1這兩種情況)和指定的k值。 我們最多可以把k個0反轉成1,請問連續唯一的最長子陣列的長度是多少? 題目的原文敘述 測試範例 Example 1: Input: nums = [1,1,1,0,0,0,1,1,1,1,
Thumbnail
題目敘述 題目會給定一個有n個整數的陣列nums和指定的k值,問我們長度為k的子陣列的平均值的最大值是多少? 題目的原文敘述 測試範例 Example 1: Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75000 Explanati
Thumbnail
題目敘述 題目會給兩個陣列nums1和nums2。 題目要求我們從中同步選擇長度為k的子序列,並且最大化子序列的分數, 回傳最高的分數值。 分數的定義: 分數 = (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] ,
Thumbnail
題目敘述 題目會給我們一個輸入整數陣列arr,和一個初始化的刪除次數k? 我們可以任意選擇從arr中刪除k個陣列元素,請問最後留下來的數字,最少會有幾個不同的數字? 註: 最後不同的數字越少越好。 題目的原文敘述 測試範例 Example 1: Input: arr = [5,5
Thumbnail
題目敘述 題目的情境是設計並且實現一個包含所有正整數的數據流,以set集合的方式存在。 數據流 = {1, 2, 3, 4, ..., ∞} 要求我們去實現定義好的function介面: SmallestInfiniteSet()建構子,初始化這個包含所有正整數的數據流。 int po
Thumbnail
隨著理財資訊的普及,越來越多台灣人不再將資產侷限於台股,而是將視野拓展到國際市場。特別是美國市場,其豐富的理財選擇,讓不少人開始思考將資金配置於海外市場的可能性。 然而,要參與美國市場並不只是盲目跟隨標的這麼簡單,而是需要策略和方式,尤其對新手而言,除了選股以外還會遇到語言、開戶流程、Ap
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
題目敘述 Find K-th Smallest Pair Distance 給定一個輸入陣列nums和 參數k。 請找出第k小的pair distance是多少? pair distance定義為 abs( nums[i] - nums[j]), i 不等於j 也就是任意兩陣列元素差值的絕對值
Thumbnail
題目敘述 Longest Arithmetic Subsequence of Given Difference 給定一個整數陣列nums,請找出給定公差difference的最長的等差數列的長度是多少?
Thumbnail
輸入給定一個已經從小到大排序好,而且彼此互質的整數陣列, 請問任取兩數分別當作分子、分母,第k小的分數是多少? 輸出請以 [分子,分母] 的形式回傳答案。
Thumbnail
題目敘述 給定一個非零陣列nums,請找出陣列裡面 最大的對偶數 是誰? 如果無解,請返回-1 對偶數定義: 整數k的對偶數是-k 例如: 99 和 -99互為對偶數。
Thumbnail
題目敘述 題目會給定一個二元陣列nums(也就是說,陣列元素只有0,1這兩種情況)和指定的k值。 我們最多可以把k個0反轉成1,請問連續唯一的最長子陣列的長度是多少? 題目的原文敘述 測試範例 Example 1: Input: nums = [1,1,1,0,0,0,1,1,1,1,
Thumbnail
題目敘述 題目會給定一個有n個整數的陣列nums和指定的k值,問我們長度為k的子陣列的平均值的最大值是多少? 題目的原文敘述 測試範例 Example 1: Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75000 Explanati
Thumbnail
題目敘述 題目會給兩個陣列nums1和nums2。 題目要求我們從中同步選擇長度為k的子序列,並且最大化子序列的分數, 回傳最高的分數值。 分數的定義: 分數 = (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] ,
Thumbnail
題目敘述 題目會給我們一個輸入整數陣列arr,和一個初始化的刪除次數k? 我們可以任意選擇從arr中刪除k個陣列元素,請問最後留下來的數字,最少會有幾個不同的數字? 註: 最後不同的數字越少越好。 題目的原文敘述 測試範例 Example 1: Input: arr = [5,5
Thumbnail
題目敘述 題目的情境是設計並且實現一個包含所有正整數的數據流,以set集合的方式存在。 數據流 = {1, 2, 3, 4, ..., ∞} 要求我們去實現定義好的function介面: SmallestInfiniteSet()建構子,初始化這個包含所有正整數的數據流。 int po