@Sukesh Not sure what's troubling you. Just use binary search.
No, seriously, my name really is Stefan. Not Stephan, Stephen, Steven or even Stefen.
Posts made by StefanPochmann
RE: Don't treat it as a 2D matrix, just treat it as a sorted list
RE: Is there's a O(log(m)+log(n)) solution? I know O(n+m) and O(m*log(n))
@greenflag What's your point? I don't see what that has to do with this thread...
RE: 7 lines, iterative, real O(1) space
@happykimi Not sure what you mean. I am considering that case. Did you overlook my
Short and fast Python
Just implementing the binary search solution using NumPy for brevity and efficiency. Gets accepted in about 260 ms, easily beating 100% in the current runtime distribution (where times range from 439 ms to 1892 ms).
import numpy as np class Solution(object): def findMaxAverage(self, nums, k): lo, hi = min(nums), max(nums) nums = np.array( + nums) while hi - lo > 1e-5: mid = nums = (lo + hi) / 2. sums = (nums - mid).cumsum() mins = np.minimum.accumulate(sums) if (sums[k:] - mins[:-k]).max() > 0: lo = mid else: hi = mid return lo
RE: "Reservoir sampling" seems inefficient
@parvez.h.shaikh said in "Reservoir sampling" seems inefficient:
I compute length
Where? I don't see it.
Also why dwell in specific random number generation when they're present in libraries :-)
Huh? I am using a library function. And a more appropriate one than you are. You're the one making it complicated.