type
status
date
slug
summary
tags
category
icon
password
Last edited time
Jan 14, 2025 01:34 PM
第一节课就是介绍了下课程的结构，会学哪些算法。
会覆盖的算法
习题
题目描述：
[!NOTE] 题目描述 Using algs4.jar. Under construction. Write a programRandomWord.javathat reads a sequence of words from standard input and prints one of those words uniformly at random. Do not store the words in an array or list. Instead, use Knuth’s method: when reading the word, select it with probability to be the champion, replacing the previous champion. After reading all of the words, print the surviving champion.
这里需要下到一个algs4.jar,我不想把他放到系统路径，所以我就把他放到我的项目路径，我的项目路径如下：
只要把java-algs4和javac-algs4里面的脚本的INSTALL替换为正确的包的路径就行：
同时我用idea把project structure设置下就行
比如java-algs4就这么写：
编译的时候就这么运行即可（我在m1的src目录下）：
这里注意下命令行参数和标准输入输出的区别
在使用 StdIn 读取标准输入时，程序会一直等待，直到检测到“输入结束”（EOF）或被强制停止。
- 在 Mac / Linux 中，按 Ctrl + D
- 在 Windows 命令行中，按 Ctrl + Z 后再按 Enter
代码：
至于这个算法的证明：
用归纳法就可以证明，直观思路就是，第一个单词被选中的概率，就是到最后还是第一个单词的概率为
这个算法也叫蓄水池抽样法，特别适合数据以流的方式到达的场景。分析下复杂度：
• 时间复杂度: O(n)
• 空间复杂度: O(1)
- 作者:很久不是自己
- 链接:https://weibo.com/article/algorithms-part1-module1
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。