2

写这个：

N = args[1].split("\\s+").length;

使用命令行参数，如： ，这是否会像我将字符串解析为字符串数组echo "A B C D E F G H I" | java Subset 3那样消耗类似的内存？"A B C D E F G H I".split()

我的评估指出（作为挑战）学​​生（我）可以尝试从 N 个字符串（上面的 N = 9，A 到 I）输入中随机均匀地显示 K 个字符串（上述 cmd 行中的 K = 3），同时消耗与 K 成比例的内存，而不是 N。所以这基本上就是我想要做的。

编辑： mvp 的回答很有帮助。现在更好地理解问题。

但我觉得我应该补充一点，我只允许使用这个：

private static Scanner scanner = new Scanner(new BufferedInputStream(System.in), charsetName);

我不能自己使用这Scanner门课，或者BufferedReader就此而言。鉴于此限制，我有点不确定如何进行。

4

3 回答 3

2

这可以解决未知长度的输入数据流（也就是说，我们只在 EOF 上停止，而不关心 N 是多少），并且将使用与 K 成正比的内存。

首先，让我们解决 K=1 的问题。如果我们开始读取输入流，我们应该假设第一项（在您的示例中为 A）应该是我们的答案 - 因为如果没有输入，那一定是它。当我们阅读第二项时，我们应该考虑将其作为我们的答案，而不是概率为1/2A。当我们阅读第 3 项 C 时，我们应该以概率1/3，以此类推。该算法将从输入流中随机选择 1 个项目，而无需预先知道项目的数量（每个项目将有相同的概率被选择）。

对于 K=2、K=3（或更多），我们采用类似的方法。例如对于 K=3，阅读 3 个项目A, B，C并将它们用作答案。当我们阅读第 4 个项目时，我们应该以3/4(K/N) 的概率选择它，并用它来替换一个等概率的活动项目1/3。然后继续这样做，直到输入流的 EOF，最后打印 3 个活动项。

于 2013-09-01T03:48:44.053 回答
1

是的，它将使用相同的方法，因为String[]无论如何都会创建一个数组作为 的结果split，即使您没有明确地将它存储在任何地方。

我建议您通过以下方式从输入中提取单词：

  1. 创建一个List wordList来存储 3 个单词。
  2. 生成一个介于 0 和输入长度减 1 之间的随机数。
  3. 如果随机数对应的位置是空白，则生成新的随机数，直到该位置不是空白。
  4. 使用最后一个随机数作为起点，返回输入搜索空格或输入的开头。这 (+1) 定义了单词的开头。
  5. 再次使用相同的随机数作为起点，在输入中继续搜索空格或输入的结尾。这 (-1) 定义了单词的结尾。
  6. 如果这个词已经在 中wordList，丢弃它并从第 2 步开始重复。
  7. 如果没有，请将其添加到列表中。
  8. 如果列表的大小小于 3，也从第 2 步开始重复。
  9. 打印列表。

在此过程中，您仅在内存中存储了 3 个字 (K)，而不是 9 (N)。

也可以通过以下方式进行扫描：

    import java.util.Scanner;

    public class MyProgram {
        public static void main(String... args) {
            final int K= 3 ;
            String[] words= new String[K] ;
            int wordCount= 0 ;
            int nextWord= 0 ;
            Scanner scanner= new Scanner(System.in) ;
            while( scanner.hasNext() ) {
                String word= scanner.next();
                wordCount++;
                if( nextWord < K ) {
                    words[nextWord]= word ;
                    nextWord++;
                } else {
                    int replacePos= (int)(Math.random()*wordCount) ; 
                    if( replacePos < K ) {
                        words[replacePos]= word ;
                    }
                }
            }
            scanner.close();
            for(String word: words ) {
                System.out.println(word);
            }
        }
    }
于 2013-09-01T03:46:37.013 回答
1

@mvp 对于情况 K = 1 有一个正确的解决方案，但是当 K > 1 时，获取项目 M 的正确概率是 K/M，而不是 1/M（在您的情况下，您应该选择概率为 3/4 的第 4 个项目，第 5 个概率为 3/5，依此类推）。

顺便说一下，这被称为水库采样。

于 2013-09-01T05:41:11.710 回答