【阿里云在线编程】 49.吃奶酪二分法

迷南。 2021-06-10 20:38 283阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 二分法 ###

做阿里云在线编程得题目感受比较大得就是，理解题目！！！

同样得，简化题目所说得，找到 `50 000` 以及左右的第一个数字，比较一下距离左边界和有边界的位置就可以了

1.  这道题目不可以用暴力法，时间复杂度会过高，所以其实这道题就是找 `50 000` 左右的数字，使用二分法即可
2.  二分法典型的左指针 `l`，右指针 `r`，中指针`mid`，二分法的条件，就是和 `50 000` 进行比较  
    如果 `nums[mid] == 50 000`，直接返回，因为 `50 000` 就是`1-100 000` 中间的数字  
    如果 `nums[mid] < 50 000`，那么就让左指针变为 `mid+1`（mid+1的目的是为了跳出循环）  
    如果 `num[mid] > 50 000`，那么就让右指针变为 `mid`
3.  最后找到了两个数字分别是 `50 000` 左边的 `nums[l-1]` 和 `50 000` 右边的 `nums[l]`，分别比较他们两个到左右边界的距离即可

### code ###

package solution49;
    
    class Solution { 
        public int solution(int n, int[] nums) { 
            if (n == 1) return Math.min(nums[0] - 1, 100_000 - nums[0]); 
            if (nums[n - 1] <= 50000) return nums[n - 1] - 1; // 如果全部数字都是小于50 000的，可以不用判断直接返回
            if (nums[0] > 50_000) return 100_000 - nums[0]; // 如果全部数字都是大于50 000的，同上
            int l = 0, r = n - 1;
            while (l < r) { 
                int mid = l + (r - l) / 2;
                if (nums[mid] == 50000) { 
                    return 49999;
                } else if (nums[mid] > 50000) { 
                    r = mid;
                } else if (nums[mid] < 50000) { 
                    l = mid + 1;
                }
            }
            return Math.max(nums[l - 1] - 1, 100_000 - nums[l]);
        }
    }

[Link 1]: https://developer.aliyun.com/coding/49
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/61b0aab2cc634bdfb234e42b743f0915.png