Blog Entries all / by tag / by year

怎样从一个未排序数组中找出第K大的数？最简单的方法便是先将数组排序，然后便可取出第K大的数了。显然，此方法有点“大材小用”，其实没必要将数组所有元素排序，只需要取出指定的元素即可。那么可不可以改进一下现有的排序算法，使之无需排序整个数组，就能找到第K大的元素呢？

我们可以将快速排序改进一下：每次基于pivot将元素分为大小两类后，舍弃目标元素不会存在于其中的那个部分。具体算法如下：

1. 选定一个pivot，将其余元素分成小于或等于pivot，以及大于pivot两类，分别记为smaller与greater
2. 记len( greater ∪ pivot ) = counter:
3. 若counter = K，表明pivot即为第K大的元素
4. 若counter > K，表明该元素在greater部分，那么smaller部分就可以舍弃无需考虑了；回到步骤1，在greater中再次寻找第K大的元素
5. 若counter < K，表明该元素在smaller部分，那么greater部分就可以舍弃；并在smaller中寻找第K-counter大的元素

前几天比较无聊，在知乎上看到有人问怎么写Flappy Bird，于是乎想自己造一个。一是为了打发时间，二是想随便找个游戏引擎，看看自己能不能快速写一个出来。游戏其实很简单，主要就是绘制鸟与随机长度的水管，然后加一个碰撞检测就行了。说起来挺简单的，但是做起来还是有一些小细节需要处理。对C++不熟悉，于是找了个Java写的游戏引擎libgdx。有了引擎，绘图什么的都能方便点。至于碰撞检测的话，发现该引擎提供了一个物理引擎，box2d，据说用它就可以进行碰撞检测了。好了，下面就讲讲怎么造一个Flappy Bird吧。

介绍了可靠数据传输原理之后，再来介绍一下TCP (Transmission Control Protocol) 原理（基于rdt）

在实际的网络传输中，channel（信道）是不可靠的，在其上传输的数据分组可能丢失，损坏，或者失序。因此需要一个可靠的数据传输协议，来保证从发送端发送的数据能够按序无损地交付给接收端。图中，应用层将传输协议视为可靠的；而在传输层中，通过可靠数据传输协议，在不可靠的网络层信道上，实现了数据的可靠传输。

两年前整理的计算机组织与体系结构复习要点

想看看Android的源码，然而在android.googlesource.com上在线查看有些不爽，不能支持代码跳转什么的，因此想把代码下载到本地用Android Studio查看。然而Git不支持下载部分子目录，得先把所有代码都clone下来才能查看。本来只想看看framework/base里面的代码，与其只下载这部分，还不如将AOSP的全部源码下载下来算了。