The pigeonhole principle

July 3, 2018

Introduction

It is very popular principle called the pigeonhole principle based on the simple math. I like to study more based on the lecture note written for the maximum gap problem.

The lecture note link is here. And it is also saved on my github.

I like to read the notes carefully and do some research on this pigeonhole principle.

Leetcode 164: Maximum gap - Distribution Sort (Radix Sort, Counting Sort) study (II)

May 10, 2015

Problem statement:

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

这道题不需要把所有的数排序 (O(nlogn), 所以, 不知道相邻的数在哪. 但是, 如果用n个桶, 每个桶有相同的长度, 这样, 排除最大距离在同一个桶中. 这样, 每个桶找到最大和最小值; 找相邻的最大和最小数的差. 这样的分析, 有些挑战, 我喜欢.

Read the article:

http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf

And then,

http://yuanhsh.iteye.com/blog/2187685

http://www.programcreek.com/2014/03/leetcode-maximum-gap-java/

http://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F

Practice the code and then figure out things learned through the process.

May 22, 2016

Read the blog, and copy the analysis from the blog as well:

http://yuanhsh.iteye.com/blog/2187685

这道题如果是O(nlgn)方法肯定很简单，排序后找最大gap就行了。但如果要求O(n)时间完成的话，难度就大大加大了。所以我们用桶排序的方法来做这道题。 有关桶排序的简介，大家可以参考维基-桶排序。我们来介绍一下桶排序的应用，桶排序就是将一定范围的值全部丢到同一个桶里。所以我们只要合理安排桶的个数，让最大的差异出现的桶与桶之间即可。假设输入的数组中的个数是n,范围从a~b。则我们会发先最大的gap一定会大于等于ceiling(b-a)/(n-1),因为如果数组是等差数列，数与数之间的差异是ceiling(b-a)/(n-1)，所以最大gap不可能比这个还小。所以我们假设让桶的容量变成ceiling(b-a)/(n-1)，那最大差异一定发生的桶之间。所以我们只要设置（b-a)/[ceiling(b-a)/(n-1)]+1个桶即可。然后就是桶之间的比较我们只需比较上一个桶的最大值和当前桶的最小值即可。所以桶里只需维护一个最大值和一个最小值。时间复杂度是O(n),空间复杂度是O(n)

Read the blog, and also like the idea to use Radix sort - check number from insignificant digit to most significant digit:
https://helloyuantechblog.wordpress.com/2015/11/17/leetcode-164-maximum-gap-hard/

Read the blog, have some code using C# in short future:
http://www.geeksforgeeks.org/radix-sort/

C# practice based on the above blog:
https://gist.github.com/jianminchen/0da5c79679d26f4682af328c922ccca9

leetcode 164: Maximum Gap - a Distribution sort (bucket, counting, radix) algorithm

Here is the leetcode link I am reading in the morning on April 4, 2015.

http://yucoding.blogspot.ca/2014/12/leetcode-question-maximum-gap.html

And then, find out myself to read this article from the following links, try to find readable explanation about the algorithms related to distribution sort algorithms.

https://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf

May 22, 2016   (30 minutes at least)

Review the solution on this blog:

https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/164.maximum-gap.java

Read blogs talking about algorithm first, 

https://ask.julyedu.com/question/213

Distribution Sort - 分布排序

Radix Sort - 基数排序

Actionable Items:

Spend 4 hours + work on code implementation, Java, C++ -> C# code.