[杂谈]15.鸽巢原理及相关OJ例题

1. 鸽巢原理

鸽巢原理又名抽屉原理、鞋盒原理&＃xff0c;是一种简单的组合数学思想&＃xff0c;在编程OJ、ACM&＃xff0c;中广泛应用&＃xff0c;往往能够达到优越的空间复杂度、时间复杂度。多用于解决存在性问题。

2. 定理证明

定理&＃xff1a; 如果把n&＃43;1个物体放入n个盒子&＃xff0c;至少有一个盒子包含两个或更多的物体。

证明&＃xff1a; 反证法 n个盒子每个盒子至多一个物品&＃xff0c;总数至多为n&＃xff0c;与有n&＃43;1个物体矛盾。
有等价定理&＃xff1a;

定理2&＃xff1a; 把m个元素放进n个集合内&＃xff0c;至少有一个集合含有k个元素&＃xff0c;其中 &＃xff1a;

• k&＃61;m/n (n整除m)

• k&＃61;[m/n]&＃43;1 (n不整除m)

定理3&＃xff1a; 把无穷多个元素放进有限个集合&＃xff0c;必然至少有一个集合里有无穷多个元素。

3. 相关例题

3.1 OJ例题

OJ 的简单应用见博主的&＃xff1a;[剑指-Offer] 3. 数组中重复的数字(哈希、抽屉原理、代码优化、多方法)

LeetCode 41. 缺失的第一个正数
LeetCode 442. 数组中重复的数据
LeetCode 448. 找到所有数组中消失的数字
《剑指-Offer》面试题3&＃xff1a;数组中重复的数字

其它相关 OJ&＃xff0c;也很多百度一下啥都有了~

3.1 组合数学相关例题

在此推荐这篇博文&＃xff1a;guoyangfan_&＃xff1a;鸽巢原理详解