peizhyi
- 浏览: 30650 次
- 性别:
- 来自: 北京
-
最新评论
-
peizhyi：
sydongda 写道有没有考虑重复的数字不好意思，好久没回来 ...
找出数组中和为N的所有配对 -
peizhyi：
zdbill 写道“存储开始的m条记录”，你不觉得前m条记录选 ...
一道算法题——从数据流中随机去m个数 -
zdbill：
“存储开始的m条记录”，你不觉得前m条记录选中的概率比后面的记 ...
一道算法题——从数据流中随机去m个数 -
sydongda：
有没有考虑重复的数字
找出数组中和为N的所有配对 -
peizhyi：
freebird0221 写道起点的选择好像不对，比如 1 ...
最长的滑道
文章列表
有一个集合a，里面有n个正整数，乱序排列。给定一个正整数N，求，a中任意两个数相加等于N，共有哪些种组合情况。例如，集合为{1,3,44,2,4,5,54,222,368} N=6,则结果集为{1,5}，{2,4}
我的思路，
1. 用N减去每个元素得到另一个数组b，嵌套循环找到a与b中值相同而位置不同的元素对；空间复杂度2N，时间复杂度O(N^2)。
2. 将a按照升序排序，初始化变量max_loc=N-1，从最小值a[i=0]开始遍历，
a. 若max_loc<=i，结束程序，否则进入b；
b. 判断a[max_loc] + a[i]与N大小关系；<N ...
题目：有一个很大很大的输入流，大到没有存储器可以将其存储下来，且只输入一次，如何从这个输入流中随机取得m个记录。我的思路：首先，存储开始的m条记录，存放于数组result[m]中；然后，假设有n条记录，每一次读取记录后，取随机数x，0<= x < n；判断随机数， 当0<= x < m时，我们将记录存放到result[x]中； 当m<= x < n时，我们不存这个记录；最后，输入所有的数据流后，result[m]存放的就是随机出来的m条记录。 分析下，我们期待的某一个记录被选中的概率为m/n，按照我的这个算法，第i个记录被选中的事件可以描述 ...