Born to be proud
7/19
2017

机试题

给夏令营学生出的机试题,虽然很简单,但要写出复杂度较低的方法并不容易。

相对排名

给定 N 个运动员的分数,计算他们的相对排名和得分最高的三个人,他们将分别获得奖项:”Gold Medal”, “Silver Medal” 和 “Bronze Medal”.

例子:

Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

Explanation: 
前三个是得分最高的三个人,他们分别获得"Gold Medal", "Silver Medal" 和 "Bronze Medal".
剩下的两名运动员,你只需根据他们的分数输出他们的相对排名.

注意:

  1. N 是不大于10000的正整数.
  2. 所有运动员的分数不会重复.

比特翻转

翻转给定的32位无符号整数。
例如,给定输入43261596(二进制为: 00000010100101000001111010011100),返回964176192(二进制为: 00111001011110000010100101000000

思考:如果这个函数被多次调用,你会怎样最优化它?

轮转有序数组中的最小值

假设一个按升序排序的数组在预先未知的某个旋转轴上旋转,

(i.e., 0 1 2 4 5 6 7 可能变为 4 5 6 7 0 1 2)

找出其中最小的元素.

你可以假设数组中没有重复值.

思考:你写的算法时间,空间复杂度为多少?