Find pivot from a stream
source link: http://siongui.github.io/2017/09/22/find-pivot-from-a-stream/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Find pivot from a stream
September 22, 2017
This is also an interesting result, although it's quite simple.
You are given a stream of distinct numbers x[0],x[1],…,x[n−1]x[0],x[1],…,x[n−1], and you are to find a pivot number from them, i.e. x[i]x[i] such that x[j]<x[i]x[j]<x[i] iff j<ij<i. If there is no such number, report it. How to do it in O(n)O(n) time with O(1)O(1) space? Since it's a stream, each number can only be accessed once unless it's stored.
Solution:
Report the smallest possible pivot number: keep a candidate pp initialized to x[0]x[0]. It is invalidated whenever we see a number smaller than itself, which will be then initialized to the next number bigger than the max we have seen so far.
post by Shen-Fu Tsai
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK