房屋结构自建设计 网站,就业seo好还是sem,如何进行网站的推广,视频添加到wordpress题目信息
LeetoCode地址: . - 力扣#xff08;LeetCode#xff09;
题目理解
想象题目提供的w数组里是很多根长短不一的棍子#xff0c;然后我们将其按顺序排列成一条线。
然后我们扔一个沙包#xff0c;砸中哪一根棍子#xff0c;就代表命中了那根棍子代表的数字。很…题目信息
LeetoCode地址: . - 力扣LeetCode
题目理解
想象题目提供的w数组里是很多根长短不一的棍子然后我们将其按顺序排列成一条线。
然后我们扔一个沙包砸中哪一根棍子就代表命中了那根棍子代表的数字。很显然棍子越长就越容易砸中。
假如这五根棍子分别长12345那么合并后总长度就是1234515
那么沙包扔出后可能会落在0到15之间的任何一个位置。具体来说落到[0,1]的可能性会比落到[1,3]小因为后者代表的区间更大而概率最大的则是[10,15],这代表了最后一根棍子的区间。
那么题目就变成了如何快速找到沙包落点属于哪一个区间。使用前缀和我们可以很轻松的表示这5根棍子的区间:[1,3,6,10,15]而这又恰巧是一个单调递增数组使用二分法可以在O(logn)的时间复杂度内找到区间。
前缀和二分写法
class Solution {int[] preSum;Random random;int l;public Solution(int[] w) {l w.length;random new Random();preSum new int[l];preSum[0] w[0];for (int i 1; il; i) {preSum[i] preSum[i-1] w[i];}}public int pickIndex() {int num random.nextInt(preSum[l-1])1;int left 0, right l-1;while (left right) {int mid left (right-left)/2;if (preSum[mid] num) {return mid;}if (preSum[mid] num) {left mid1;} else {right mid-1;}}return preSum[left] num ? left : left1;}
}/*** Your Solution object will be instantiated and called as such:* Solution obj new Solution(w);* int param_1 obj.pickIndex();*/ 写法2
