Measure Zero

Oct 21, 2019

线性时间找中位数, 以及两个排序数组找中位数

Last Updated on Jun 7, 2020. 简单地实现了一遍.

找中位数最暴力的方法是先排序再取中位数, 时间复杂度 . 后来才得知中位数有时间复杂度的算法, 事实上任意顺序统计量都可以用时间找出.

Lights-Out

Each employee of MegaCorp has a separate office in the MegaCorp office building. Each office is equipped with one overhead light and one toggle switch to turn the light on and off.

Every day, the employees turn on all lights when they come to work. Each evening they turn off all lights when they go home.

One day, the employees arrive to discover that someone has played a rather elaborate hoax on them. Though all looks fine when they come in (all lights are off), every time an employee flicks the switch in her office, this not only toggles the light in her office, but also the lights in the offices of all of her friends. (Friendship is a symmetric relationship.)

The question: does there necessarily exist an arrangement of the switches that will turn all lights simultaneously on (so that work can begin)? Prove your answer.

Super Egg Drop

You are given eggs, and you have access to a building with floors from to .

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor with such that any egg dropped at a floor higher than will break, and any egg dropped at or below floor will not break.

Each move, you may take an egg (if you have an unbroken one) and drop it from any floor (with ).

Your goal is to know with certainty what the value of is.

What is the minimum number of moves that you need to know with certainty what is, regardless of the initial value of ?