Ruby 几道有趣的 leetcode 题目
今天刚刚做完第 200 道 leetcode 题目。说说自己的感受，并分享两道有趣的题目。
1.运行时间排名 只有相同语言的排名才有意义。我原先以为 ruby 比 python 快，有时确实如此，但也不确定。前几天看了个 leetcode 的 discuss 帖子，说某题用 python 比 C++ 要快很多----都知道 C、C++ 在时间排名上一般总高于其他语言。系统管理员 1337coder 的回复大概是与机器等配置有关，用户不宜以此和其他语言做对比。
运行时间排名十分不稳定，这可能与目前 ruby 的提交量太少有关，但也与服务器有关。我的猜测是，如果有相邻两个时间分布式相同的，那得到这两种分布的概率是相同的。比如下图，92ms 和 104ms 的运行时间有相同的分布。如果这次运行时间是 92ms，下次也可能是 104ms。
- 做题训练很有价值
这两百道题，至少有 170 道题目是自己想出来然后一行行 coding 提交 AC 的。现在回顾前面一百题，已经感觉自己原先的方法十分拙劣了。这算是做题的一个收获。
3.两道有趣的题目 3.1 majority elements 求一个元素中出现次数最多的元素。这个题目的常规解法是使用优化后的动态规划。遍历一遍数组得到结果。但一个更有效的方法是排序。先上代码
def majority_element(nums)
nums.sort[nums.size/2]
end
其实上面的分布图就是该题使用排序法得到的结果，该法的运行时间明显优于其他方法。但是排序时间复杂度为 O(nlogn)，为何这里特别快？ 记得库函数中的 sort 方法都是三路快排加插入排序。在该题中，由于至少有一般的元素是相同的，所以插入的过程应该是直接插入尾部，这样时间几乎接近线性。但和传统方法比又少了若干次比较，所以更快。该法思路来源于同组同学。
3.2 find first missing one. 找出一个乱序数组中缺少的第一个正数。如 [4, 0 ,3,1] 缺少的第一个正数是 2。 这题一般的思路是直接将正数值放入其对应下标，然后按序遍历数组，找到和值不对应的下标即为所缺。但这样仍然需要多次比较和读写数组（尽管是线性复杂度）。本人的思路如代码所示：
def first_missing_positive(nums)
oldBase, base=0,0
arr=[nums,nums.reverse]
i=0
loop do
arr[i].each { |e| base=e if e==base+1 }
break if base==oldBase
oldBase,i=base,1-i
end
return base+1
end
首先记录当前已有的值（初始为零），然后按序遍历数组，如果 1 出现了，就找 2，2 出现了就找 3，直到找到为止。为了加速移动，并应对数组已经有序的情况，在正序遍历数组后再逆序遍历数组。和常规方法相比，该法的复杂度是 O(n*n)。但只要输入序列不是锯齿状（如快排的 killer adversary, 又如 [2,4,1,3]），该法在除锯齿状数据的情况以外运行时间都很短。在随机产生数据的前提下，我对两种思路的数据都做了实验，O(n*n) 的解法要快于 O(n) 法。但如果数据是用 knuth shuffle 洗牌的思路生成随机数组（如 [4,2,1,3]），只是将原组做了交换，缺失值为最大值的情况下，该法将产生很多循环，运行效果变差（在对 10000 个连续值 shuffle 后的数组处理）。用这种思路解题，运行时间 76ms，和其他方法的最优时间相同。
最后感谢关注了 leetcodePractice 的各位朋友，是你们带给我更大动力。特别感谢@quakewang，对我提出了许多批评的同时展示了许多书写良好的代码。
本人 LeetcodePractice 项目地址：https://github.com/acearth/LeetCodePractice
欢迎批评和关注！
下班前刚好刷到了 majority_element 这题，解法一模一样，我管它叫 fast and simple and cheat 另外贴一下三分之一那个问题的解法，正巧是从 @luikore 那里学到的：
def majority_element(nums)
nums.sort.chunk{|x|x}.map(&:last).inject([]){|m,v| m << v[0] if v.size > nums.size / 3;m}
end
3.2 这样比较简单
def first_missing_positive(nums)
b = Array.new nums.size + 1
b[0] = true
nums.each do |n|
b[n] = true if n > 0
end
b.index nil or b.size
end
循环体内尽量少做运算就可以
其实 Ruby 的 bignum 实现用到的一个 bitset 的函数 nlz 可以调用 GCC 的 __builtin_clz, 而 __builtin_clz 会转换成处理器的 bsr/clz 指令，用 bitset 做这个运算，就可以少用很多内存，降低程序的 memory bandwidth. 而且 128 bit 的 clz 指令可以把第二次遍历的最后一次运算降低到 1/128
不过 bignum 并没有暴露 "set nth bit" 的 interface... 就做不到 C 的程度了
bitset + __builtin_clz:
#include <stdlib.h>
#include <memory.h>
typedef unsigned long l;
int firstMissingPositive(int* nums, int numsSize) {
if (!numsSize) {
return 1;
}
int llen = ((numsSize + sizeof(l) - 1) / sizeof(l));
int lbits = sizeof(l) * 8;
l* arr = malloc((llen + 1) * sizeof(l));
// unset first bit
memset(arr, 0xFF, (llen + 1) * sizeof(l));
arr[0] &= ~(1UL << (lbits - 1));
for (int i = 0; i < numsSize; i++) {
if (nums[i] > 0) {
int j = nums[i] / lbits;
int k = nums[i] % lbits;
arr[j] &= ~(1UL << ((lbits - 1) - k));
}
}
int res = 0;
for (int i = 0; i < llen; i++) {
if (arr[i]) {
res += __builtin_clzl(arr[i]);
break;
} else {
res += lbits;
}
}
free(arr);
return res;
}
3.1 的正常解
def majority_element(nums)
cnt = 0
num = nums.first
nums.each do |n|
next cnt += 1 if n == num
cnt -= 1
cnt, num = 1, n if cnt < 0
end
num
end
拿了 88ms，好像并不算太慢。如果输入数据量很大的话排序可能会比遍历慢。
3.2 的 2B 解
def first_missing_positive(nums)
tail = {}
nums.each do |v|
next if v <= 0
next if tail[v]
tail[v] = v
if tail[v-1]
tail[v] = tail[v-1]
tail[tail[v]] = v
end
if tail[v+1]
last = tail[v+1]
tail[last] = tail[v]
tail[tail[v]] = last
end
end
tail[1] ? tail[1]+1 : 1
end
拿了 80ms
➜ ~ PRY
[1] pry(main)> def majority_element(nums)
[1] pry(main)* cnt = 0
[1] pry(main)* num = nums.first
[1] pry(main)* nums.each do |n|
[1] pry(main)* next cnt += 1 if n == num
[1] pry(main)* cnt -= 1
[1] pry(main)* cnt, num = 1, n if cnt < 0
[1] pry(main)* end
[1] pry(main)* num
[1] pry(main)* end
=> nil
[2] pry(main)> a=[1,2,1,1,1,1,2,3,2,3,2,3,2,3,2,3,3,3]
=> [1, 2, 1, 1, 1, 1, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3]
[3] pry(main)> majority_element a
=> 3
[4] pry(main)> a = [1,5,7,3,4,2,3,4,2,2,2,1,2,6,4,3,2,1,7,5,6,4,2,1,1]
=> [1, 5, 7, 3, 4, 2, 3, 4, 2, 2, 2, 1, 2, 6, 4, 3, 2, 1, 7, 5, 6, 4, 2, 1, 1]
[5] pry(main)> majority_element a
=> 1
[6] pry(main)>
@msg7086 请问第二个数组是什么情况？
You may assume that the array is non-empty and the majority element always exist in the array.
