908. Smallest Range I (最小差值 I)
更新於 發佈於 閱讀時間約 1 分鐘
↑看個小廣告，支持好內容↑
讀懂這段在表達啥，這題就算解掉一半了
陣列中的每項都有一次調整的機會，可以被任意改成nums[i]-k~nums[i]+k之間的整數，而我們的目標是：盡可能縮小陣列的全距 (最大值－最小值)。
似乎很直觀，就把小的數字變大一點、大的數字變小一點就好了對吧？
// 成功的案例
nums=[1,9], k=2: 1→3、9→7，全距=4
// 失敗的案例
nums=[5,7], k=3: 5→8、7→4，全距=4
(顯然不對，這比調整前的差距還大)
事實上，直接把 5 改成 7，兩數就相同了，故正確答案應該是 0；即便我們在陣列加入很多很多 6，他們照樣可以被改成 7，並不影響結果。綜上，我們得到兩個結論：
- 最小範圍確實是由 [max, min] 所決定。
- 差值不會為負，當
max-min-2*k<0，答案必定為 0。
[備註] 這題因為文字敘述收到許多負評，但我認為它是刻意為之的，如何在有限時間內消化提取線索解題，也是邏輯與閱讀素養的一大考驗。話說回來，把蕪雜的需求化約進程式設計，這本身就是開發實務的縮影哪～ (茶
- 本題分類標籤：
Array、Math - 本題正解率＝
69.3％
❤️ 若內容對你實用，歡迎追蹤本專題，或小額贊助支持～
⭐ 這是我的第 13 篇刷題筆記，完整解題索引看這裡 → Here
留言0
查看全部
你可能也想看
Google News 追蹤
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
題目敘述 Find K-th Smallest Pair Distance
給定一個輸入陣列nums和 參數k。
請找出第k小的pair distance是多少?
pair distance定義為 abs( nums[i] - nums[j]), i 不等於j
也就是任意兩陣列元素差值的絕對值
題目敘述 Longest Arithmetic Subsequence of Given Difference
給定一個整數陣列nums，請找出給定公差difference的最長的等差數列的長度是多少?
給定一個整數陣列nums，請找出等最長差數列的長度是多少?
輸入給定一個已經從小到大排序好，而且彼此互質的整數陣列，
請問任取兩數分別當作分子、分母，第k小的分數是多少?
輸出請以 [分子，分母] 的形式回傳答案。
題目敘述
給定一個非零陣列nums，請找出陣列裡面 最大的對偶數 是誰?
如果無解，請返回-1
對偶數定義: 整數k的對偶數是-k
例如: 99 和 -99互為對偶數。
題目敘述
題目會給定一個二元陣列nums(也就是說，陣列元素只有0,1這兩種情況)和指定的k值。
我們最多可以把k個0反轉成1，請問連續唯一的最長子陣列的長度是多少?
題目的原文敘述
測試範例
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,
題目敘述
題目會給定一個有n個整數的陣列nums和指定的k值，問我們長度為k的子陣列的平均值的最大值是多少?
題目的原文敘述
測試範例
Example 1:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanati
題目敘述
題目會給兩個陣列nums1和nums2。
題目要求我們從中同步選擇長度為k的子序列，並且最大化子序列的分數，
回傳最高的分數值。
分數的定義:
分數 =
(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) *
min(nums2[i0] ,
題目敘述
題目會給我們一個輸入整數陣列arr，和一個初始化的刪除次數k？
我們可以任意選擇從arr中刪除k個陣列元素，請問最後留下來的數字，最少會有幾個不同的數字?
註: 最後不同的數字越少越好。
題目的原文敘述
測試範例
Example 1:
Input: arr = [5,5
題目敘述
題目的情境是設計並且實現一個包含所有正整數的數據流，以set集合的方式存在。
數據流 = {1, 2, 3, 4, ..., ∞}
要求我們去實現定義好的function介面:
SmallestInfiniteSet()建構子，初始化這個包含所有正整數的數據流。
int po
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
題目敘述 Find K-th Smallest Pair Distance
給定一個輸入陣列nums和 參數k。
請找出第k小的pair distance是多少?
pair distance定義為 abs( nums[i] - nums[j]), i 不等於j
也就是任意兩陣列元素差值的絕對值
題目敘述 Longest Arithmetic Subsequence of Given Difference
給定一個整數陣列nums，請找出給定公差difference的最長的等差數列的長度是多少?
給定一個整數陣列nums，請找出等最長差數列的長度是多少?
輸入給定一個已經從小到大排序好，而且彼此互質的整數陣列，
請問任取兩數分別當作分子、分母，第k小的分數是多少?
輸出請以 [分子，分母] 的形式回傳答案。
題目敘述
給定一個非零陣列nums，請找出陣列裡面 最大的對偶數 是誰?
如果無解，請返回-1
對偶數定義: 整數k的對偶數是-k
例如: 99 和 -99互為對偶數。
題目敘述
題目會給定一個二元陣列nums(也就是說，陣列元素只有0,1這兩種情況)和指定的k值。
我們最多可以把k個0反轉成1，請問連續唯一的最長子陣列的長度是多少?
題目的原文敘述
測試範例
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,
題目敘述
題目會給定一個有n個整數的陣列nums和指定的k值，問我們長度為k的子陣列的平均值的最大值是多少?
題目的原文敘述
測試範例
Example 1:
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanati
題目敘述
題目會給兩個陣列nums1和nums2。
題目要求我們從中同步選擇長度為k的子序列，並且最大化子序列的分數，
回傳最高的分數值。
分數的定義:
分數 =
(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) *
min(nums2[i0] ,
題目敘述
題目會給我們一個輸入整數陣列arr，和一個初始化的刪除次數k？
我們可以任意選擇從arr中刪除k個陣列元素，請問最後留下來的數字，最少會有幾個不同的數字?
註: 最後不同的數字越少越好。
題目的原文敘述
測試範例
Example 1:
Input: arr = [5,5
題目敘述
題目的情境是設計並且實現一個包含所有正整數的數據流，以set集合的方式存在。
數據流 = {1, 2, 3, 4, ..., ∞}
要求我們去實現定義好的function介面:
SmallestInfiniteSet()建構子，初始化這個包含所有正整數的數據流。
int po