Java 在流中查找中值

Question

我试图在 Java 的输入流中找到中位数。在每个用户输入之后，应该有一个更新新中位数的输出。例子：读取流 5 的第一个元素后，中位数为 5 读取流 5 的第 2 个元素后，15 的中位数为 10 读取流 5、15、1 的第 3 个元素后，中位数为 5 读取流5、15、1、3的第4个元素后中位数为4，依此类推

到目前为止，这是我的代码，但它不适用于超过 4 的输入。

public static void main(String[] args){
    Scanner s = new Scanner(System.in); 
    System.out.print("Enter a integer for number of streams: ");
    int n=s.nextInt();
    int[] x=new int[n];
    for(int i=0;i<n;i++) {
        System.out.println("Enter a integer: ");
        x[i]=s.nextInt();
        if(i==0) { //first input number
            System.out.println(x[i]+" goes to stream --> Median is: "+x[i]);
        }
        else if(i==1) {   //when i =1, it is technically second input 
            System.out.println(x[i]+" goes to stream --> Median is: "+(float)(x[i]+x[0])/2);
        }
        else if(i>=2 && i%2==0) {  //3rd input so # of inputs is odd        
            Arrays.sort(x);
            System.out.println(x[i]+" goes to stream --> Median is: "+x[n/2]);
        }
        else if(i>=3 && i%2!=0) {  //when # of input is more than 3 and even
            Arrays.sort(x);
            int j=n/2;
            float med=(x[j]+x[j-1])/2;
            System.out.println(x[i]+" goes to stream --> Median is: "+med);
        }

我还没有完成，但我的问题是：这种方法有效吗？基本上我只是使用迭代器 i 来查看输入的 # 是奇数还是偶数。如果是奇数，对输入数组进行排序，并找到中间的#。如果偶数，找到中间的2个加除。我见过其他使用堆等的解决方案，但我只是严格使用数组。

Answer 1

您的代码看起来不错，显然它可以改进，因为它是一种幼稚的方法。

我在您的解决方案中看到的错误是您在第 3 和第 4 个 else-if 块中使用 n（完整数组的长度）而不是 i（当前长度）

此外，使用 ArrayList 而不是 Array，因为数组被初始化为其默认值（此处为 0），因此您会得到错误的输出。

尝试使用以下更正：

public static void main(String[] args){
    Scanner s = new Scanner(System.in); 
    System.out.print("Enter a integer for number of streams: ");
    int n=s.nextInt();
    List<Integer> x = new ArrayList<>();
    for(int i=0;i<n;i++) {
        System.out.println("Enter a integer: ");
        x.add(s.nextInt());
        if(i==0) { //first input number
            System.out.println(x.get(i)+" goes to stream --> Median is: "+x[i]);
        }
        else if(i==1) {   //when i =1, it is technically second input 
            System.out.println(x.get(i)+" goes to stream --> Median is: "+(float)(x.get(i)+x.get(0))/2);
        }
        else if(i>=2 && i%2==0) {  //3rd input so # of inputs is odd        
            Collections.sort(x);
            System.out.println(x.get(i)+" goes to stream --> Median is: "+x.get(i/2));
        }
        else if(i>=3 && i%2!=0) {  //when # of input is more than 3 and even
            Collections.sort(x);
            int j=i/2;
            float med=(x.get(j)+x.get(j-1))/2;
            System.out.println(x.get(i)+" goes to stream --> Median is: "+med);
        }
 }
}

现在，让我们谈谈时间复杂度。

正如我在上面所说的，这是一种 天真的方法 。下一步可以是提高时间复杂度，这可以通过使用数据结构来存储元素来完成，元素在每次添加时自行排序，而不是我们每次都排序。我的意思是如果我们使用某种 SortedList.

但是，在java中没有class如SortedList。但是有一个 class 是基于类似的概念，即 PriorityQueue。我建议您阅读它并尝试自己降低复杂性。

Java 在流中查找中值

Java Find Median in Stream

java

median