天天看點

Leetcode: 倆球之間的磁力

題目

在代号為 C-137 的地球上,Rick 發現如果他将兩個球放在他新發明的籃子裡,它們之間會形成特殊形式的磁力。Rick 有 n 個空的籃子,第 i 個籃子的位置在 position[i] ,Morty 想把 m 個球放到這些籃子裡,使得任意兩球間 最小磁力 最大。

已知兩個球如果分别位于 x 和 y ,那麼它們之間的磁力為 |x - y| 。

給你一個整數數組 position 和一個整數 m ,請你傳回最大化的最小磁力。

示例:

輸入:position = [1,2,3,4,7], m = 3
輸出:3
解釋:将 3 個球分别放入位于 1,4 和 7 的三個籃子,兩球間的磁力分别為 [3, 3, 6]。最小磁力為 3 。我們沒辦法讓最小磁力大于 3 。      
輸入:position = [5,4,3,2,1,1000000000], m = 2
輸出:999999999
解釋:我們使用位于 1 和 1000000000 的籃子時最小磁力最大。      

解題思路

1.兩球的最小距離的最小值,是1;最小距離的最大值是 (最後位置的球坐标 - 最前位置的球坐标) / (球數-1),這裡需要先對position數組排序,那麼易得最小球間距離的最大值為 (position[position.length - 1] - position[0]) / (m-1)。

2.有最小和最大,直覺想到二分法。以二分的中間值,作為間距去擺放球。如果擺放的球數 >=m, 可認為需要增加球間距 (同時儲存中間值作為候選答案); 否則需要減少球間距。

代碼實作

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int left = 1, right = position[position.length - 1] - position[0], ans = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (check(mid, position, m)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    public boolean check(int x, int[] position, int m) {
        int pre = position[0], cnt = 1;
        for (int i = 1; i < position.length; i++) {
            if (position[i] - pre >= x) {
                pre = position[i];
                cnt += 1;
            }
        }
        return cnt >= m;
    }
}      

最後

  • 時間複雜度:O(nlog(nS)),其中 n 為籃子的個數,S 為籃子位置的上限。
  • 空間複雜度:O(logn),即為排序需要的棧空間。
  • ​​# UE4:來為我們的角色制作一個血條吧​​
  • ​​使用 Google Breakpad 來助力解決程式崩潰​​
  • ​​UE4 多人遊戲伺服器探索​​
  • ​​使用虛幻引擎自動化工具實作自動化部署​​
  • ​​如何在 UE4 中制作一扇自動開啟的大門​​
  • ​​如何在 UE4 中用代碼去控制角色移動​​
  • ​​如何給 UE4 場景添加遊戲角色​​
  • ​​UE4:Android 平台開發實踐指南​​
  • ​​UE4 開發避坑指南(持續更新)​​
  • ​​新年開工啦,放個小煙花慶祝一下​​
  • ​​聊聊與蘋果稽核員的愛恨情仇(下)​​
  • ​​聊聊與蘋果稽核員的愛恨情仇(上)​​
  • ​​一名普通工具人的 2021 | 2021年終總結​​
  • ​​二叉樹刷題總結:二叉搜尋樹的屬性​​
  • ​​二叉樹總結:二叉樹的屬性​​
  • ​​二叉樹總結:二叉樹的修改與構造​​
  • ​​StoreKit2 有這麼香?嗯,我試過了,真香​​
  • ​​看完這篇文章,再也不怕面試官問我如何構造二叉樹啦!​​
  • ​​那幫做遊戲的又想讓大家氪金,太壞了!​​
  • ​​手把手帶你撸一個網易雲音樂首頁 | 适配篇​​
  • ​​手把手帶你撸一個網易雲音樂首頁(三)​​
  • ​​手把手帶你撸一個網易雲音樂首頁(二)​​
  • ​​手把手帶你撸一個網易雲音樂首頁(一)​​
  • ​​代碼要寫注釋嗎?寫你就輸了​​
  • ​​Codable釋出這麼久我就不學,摸魚爽歪歪,哎~就是玩兒​​
  • ​​iOS 優雅的處理網絡資料,你真的會嗎?不如看看這篇​​
  • ​​UICollectionView 自定義布局!看這篇就夠了​​
  1. 關注公衆号--- HelloWorld傑少