作者归档：在线疯狂

题目描述：

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in ...

题目描述：

Given a non-zero positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

题目大意：

给定一个正整数，返回其在Excel表格中对应的列标题。 ...

题目描述：

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return ...

题目描述：

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character. ...

基数排序（Radix Sort）、桶排序（Bucket Sort）和计数排序（Counting Sort）都是非比较排序算法。也就是说，它们并不是通过比较元素之间的大小关系来进行排序的。

首先，让我们看看三种排序算法的时间复杂度：

基数排序：O(dn) (d次调用桶排序)，空间复杂度 O(k) (稍后详解)

桶排序：O(n)时间复杂度，O(n)空间复杂度

计数排序：O(n)时间复杂度，O(k)空间复杂度，每一个元素都是整数，并且位于0到k - 1之间

计数排序

假设：数组中的每一个元素都位于[0, k-1]的区间内

算法：此处不做详细描述

它是一种稳定排序：

时间复杂度：O(n)

空间复杂度：O(k)

基数排序

假设：它基于下面的假设：

k1 k2 k3 ... kd，其中对于每一个元素ki均位于[0, k-1]的范围内，ki是数字。k是键(key)的基(base)。如果k=10，则键就是一个十进制数。

算法过程如下：

对于每一个数位，按照这一位对数组执行计数排序。

算法假设每一次调用计数排序时，结果都是一次稳定的排序。否则基数排序就行不通了。

时间复杂度：O(dn) 

空间复杂度：O(k)

显然，你可以通过增加k值减少d，同时牺牲一部分空间。

桶排序

假设:它使用了具有固定范围的“桶”。它假设每一个元素都会落在这些桶内。每一个桶的范围是固定的。如果桶的范围是1，则该算法就与计数排序很相似了，唯一的不同之处是，它存储的是元素本身而不是它们的计数。

算法：

假设有k个桶：B0, B1, ... ...