Java 中流式运行整数的中位数

2024年9月10日 | 阅读 12 分钟

给定一个整数数组。计算输入数组中到目前为止遍历的元素的中间值。为简单起见，假设没有重复项。

示例

输入

int arr[] = {17, 11, 15, 13, 10, 12, 18, 19, 1, 16, 14, 20};

输出 {17, 14, 15, 14, 13, 12, 13, 14, 13, 14, 14, 14.5}

解释：我们从左到右开始读取数组。遍历的第一个元素是 17。因此，中位数是 17。因为只遍历了一个元素。之后，遍历了元素 11。现在，此时，我们已经遍历了两个元素 17 和 11。因此，中位数变为 (11 + 17) / 2 = 14。

之后，遍历了元素 15。现在我们总共有 3 个遍历过的元素，17、11 和 15，而奇数个元素的中间值是元素按升序排列时的中间元素。因此，这三个元素的中间值是 {11, 15, 17} => {15}。

现在，元素 13 进入了视野，总共遍历了 4 个元素，而偶数个元素的中间值是排序后两个中间元素的平均值。因此，当前中间值为：{11, 13, 15, 17} => (13 + 15) / 2 = 14。类似地，我们也可以计算其他中间值。

方法：使用插入排序

从上面的例子可以看出，为了计算中间值，需要对目前为止遍历过的整数进行排序。因此，我们需要一种排序技术来对元素进行排序。我们将使用插入排序来对元素进行排序。

文件名：RunningIntegerStream.java

public class RunningIntegerStream 
{

// Method that finds the position for inserting the current element 
// into the stream with the help of binary search.
static int binarySearch(int inputArr[], int ele, int l, int h)
{
if (l >= h) 
{
return (ele > inputArr[l]) ? (l + 1) : l;
}

int midIndex = (l + h) / 2;

if (ele == inputArr[midIndex])
{
return midIndex + 1;
}

// recursively finding the appropriate index for the element ele
if (ele > inputArr[midIndex])
{
return binarySearch(inputArr, ele, midIndex + 1, h);
}

return binarySearch(inputArr, ele, l, midIndex - 1);
}

// Method that displays the median of running or stream integers
public void displayMedian(int inputArr[], int s)
{
int a, b, position, number;
int countEle = 1;

System.out.println("Median after reading element " + inputArr[0] + " is: " + inputArr[0]);

for (a = 1; a < s; a++) 
{
float median;
b = a - 1;
number = inputArr[a];

// find the position to insert the current element in sorted
// part of the array
position = binarySearch(inputArr, number, 0, b);

// move elements to the right to create space to insert
// the current element
while (b >= position) 
{
inputArr[b + 1] = inputArr[b];
b = b - 1;
}

inputArr[b + 1] = number;

// increment count of sorted elements in the array
countEle = countEle + 1;

// if we have traversed only the odd number of elements, then
// the median is the middle element when the elements are sorted.
// else the median is an average of two middle elements.

if (countEle % 2 != 0) 
{
median = inputArr[countEle / 2];
}
else 
{
median = (float)(inputArr[(countEle / 2) - 1] + (float)inputArr[countEle / 2]) / 2f;
}
System.out.print( "Median after reading { ");
for(int i = 0; i < a + 1; i++)
{
System.out.print(inputArr[i] + " ");
}
System.out.println( "} elements is " + median );
}
}


// main method
public static void main (String[] argvs) 
{
// creating an object of the class RunningIntegerStream
RunningIntegerStream obj = new RunningIntegerStream();
int inputArr[] = { 17, 11, 15, 13, 10, 12, 18, 19, 1, 16, 14, 20 };
int s = inputArr.length;

// invoking the method displayMedian
obj.displayMedian(inputArr, s);
}
}

输出

Median after reading element 17 is: 17
Median after reading { 11 17 } elements is 14.0
Median after reading { 11 15 17 } elements is 15.0
Median after reading { 11 13 15 17 } elements is 14.0
Median after reading { 10 11 13 15 17 } elements is 13.0
Median after reading { 10 11 12 13 15 17 } elements is 12.5
Median after reading { 10 11 12 13 15 17 18 } elements is 13.0
Median after reading { 10 11 12 13 15 17 18 19 } elements is 14.0
Median after reading { 1 10 11 12 13 15 17 18 19 } elements is 13.0
Median after reading { 1 10 11 12 13 15 16 17 18 19 } elements is 14.0
Median after reading { 1 10 11 12 13 14 15 16 17 18 19 } elements is 14.0
Median after reading { 1 10 11 12 13 14 15 16 17 18 19 20 } elements is 14.5

复杂度分析：程序使用了插入排序技术。因此，程序的 time complexity 为 O(n²)。程序不使用任何数据结构。因此，程序 space complexity 为常数，即 O(1)。

注意：有人可能会争论为什么程序中使用了插入排序技术。也可以使用其他排序技术，例如选择排序、归并排序等。这样做的原因是，在插入排序的任何给定实例中，例如对第 k 个元素进行排序，输入数组的前 k 个元素已排序。插入排序不依赖于即将到来的数据（未来数据）来对当前的数据进行排序。换句话说，插入排序在插入下一个元素时对到目前为止的数据进行排序。这是插入排序的一个重要方面，使得该算法成为一个在线算法。

方法：使用 AVL 树

使用 AVL 树，可以找到流式整数的中位数。我们将一个接一个地将元素插入 AVL 树，并跟踪

文件名：RunningIntegerStream1.java

class TreeNode 
{
int key;
int freq; // the number of times an element occurs in the stream
int lSubTreeCount; // total number of nodes present in the in the left subtree
int rSubTreeCount; // total number of nodes present in the right subtree
int hght; // height for doing the AVL operations
TreeNode lft;
TreeNode rght;

TreeNode(int key) 
{
this.key = key;
hght = 1;
lft = rght = null;
lSubTreeCount = rSubTreeCount = 0;
freq = 1;
}
}

class AVL 
{
TreeNode root;
int size;

AVL() {
size = 0;
root = null;
}

void insert(int key) {
root = insertHelper(root, key);
}

TreeNode leftR(TreeNode x) 
{
TreeNode y = x.rght;
TreeNode T = y.lft;

// Performing the rotation
y.lft = x;
x.rght = T;

// Updating the heights
x.hght = Math.max(findHeight(x.lft), findHeight(x.rght)) + 1;
y.hght = Math.max(findHeight(y.lft), findHeight(y.rght)) + 1;

// updating the count
x.rSubTreeCount = (T != null) ? T.lSubTreeCount + T.rSubTreeCount + T.freq : 0;
y.lSubTreeCount = x.lSubTreeCount + x.rSubTreeCount + x.freq;

// Return new root
return y;
}

TreeNode rightR(TreeNode y) 
{
TreeNode x = y.lft;
TreeNode T = x.rght;

// Performing the rotation
x.rght = y;
y.lft = T;

// Update heights
y.hght = Math.max(findHeight(y.lft), findHeight(y.rght)) + 1;
x.hght = Math.max(findHeight(x.lft), findHeight(x.rght)) + 1;

// updating the count
y.lSubTreeCount = (T != null) ? T.lSubTreeCount + T.rSubTreeCount +T.freq : 0;
x.rSubTreeCount = y.lSubTreeCount + y.rSubTreeCount + y.freq;

// Returning the new root
return x;
}

// finding the difference in heights between the 
// left and the right subtrees
int findBalance(TreeNode root) 
{
if (root == null)
{
return 0;
}
return findHeight(root.lft) - findHeight(root.rght);
}

// finding the height of the tree
int findHeight(TreeNode root) 
{
if (root == null)
{
return 0;
}
return root.hght;
}

TreeNode insertHelper(TreeNode root, int key) 
{
// inserting the key into the tree
// incrementing the size
if (root == null) 
{
size = size + 1;
return new TreeNode(key);
}

if (key < root.key) 
{
root.lft = insertHelper(root.lft, key);
root.lSubTreeCount++;
}

else if (key > root.key) 
{
root.rght = insertHelper(root.rght, key);
root.rSubTreeCount++;
}

else {
root.freq++;
size = size + 1;
return root;
}

// insertion is done, update the height and check for balancing factor
root.hght = 1 + Math.max(findHeight(root.lft), findHeight(root.rght));

int balance = findBalance(root);

// If the node is getting unbalanced, then there
// are following four cases 

// Left Left Case
if (balance > 1 && key < root.lft.key)
{
return rightR(root);
}

// Right Right Case
if (balance < -1 && key > root.rght.key)
{
return leftR(root);
}

// Left Right Case
if (balance > 1 && key > root.lft.key) 
{
root.lft = leftR(root.lft);
return rightR(root);
}

// Right Left Case
if (balance < -1 && key < root.rght.key) 
{
root.rght = rightR(root.rght);
return leftR(root);
}

// returning the unchanged node pointer that is unchanged
return root;

}

float findMedian() 
{
// as per the size (either even or odd) look for the element(s) that are required to find
// out the median
int indx = size / 2 + 1;
int k1 = 0; 
int k2 = 0;
float medianVal = 0;

k1 = findEle(root, indx);
medianVal = k1 / 1.0f;
if (size % 2 == 0) 
{
k2 = findEle(root, indx - 1);
medianVal = (k1 + k2) / 2.0f;
}
return medianVal;
}

int findEle(TreeNode root, int indx) 
{

if (indx >= root.lSubTreeCount + 1  && indx < root.lSubTreeCount + 1 + root.freq)
{
return root.key;
}

else if (indx <= root.lSubTreeCount)
{
return findEle(root.lft, indx);
}

else
{
return findEle(root.rght, indx - root.lSubTreeCount - root.freq);
}
}


}

public class RunningIntegerStream1 
{

// Method that displays the median of running or stream integers
public void displayMedian(int inputArr[], int s)
{
int a, b, position, number;
int countEle = 1;

System.out.println("Median after reading element " + inputArr[0] + " is: " + inputArr[0]);

AVL avl = new AVL();

avl.insert(inputArr[0]);

for (a = 1; a < s; a++) 
{
float median;
avl.insert(inputArr[a]);
median = avl.findMedian();

System.out.print( "Median after reading { ");
for(int i = 0; i < a + 1; i++)
{
System.out.print(inputArr[i] + " ");
}
System.out.println( "} elements is " + median );
}
}

// main method
public static void main (String[] argvs) 
{
// creating an object of the class RunningIntegerStream1
RunningIntegerStream1 obj = new RunningIntegerStream1();
int inputArr[] = { 17, 11, 15, 13, 10, 12, 18, 19, 1, 16, 14, 20 };
int s = inputArr.length;

// invoking the method displayMedian
obj.displayMedian(inputArr, s);
}
}

输出

Median after reading element 17 is: 17
Median after reading { 17 11 } elements is 14.0
Median after reading { 17 11 15 } elements is 15.0
Median after reading { 17 11 15 13 } elements is 14.0
Median after reading { 17 11 15 13 10 } elements is 13.0
Median after reading { 17 11 15 13 10 12 } elements is 12.5
Median after reading { 17 11 15 13 10 12 18 } elements is 13.0
Median after reading { 17 11 15 13 10 12 18 19 } elements is 14.0
Median after reading { 17 11 15 13 10 12 18 19 1 } elements is 13.0
Median after reading { 17 11 15 13 10 12 18 19 1 16 } elements is 14.0
Median after reading { 17 11 15 13 10 12 18 19 1 16 14 } elements is 14.0
Median after reading { 17 11 15 13 10 12 18 19 1 16 14 20 } elements is 14.5

复杂度分析：在 AVL 树中，插入元素的 time complexity 为 O(log(n))。因此，程序的 overall time complexity 为 O(n x log(n))。程序为 AVL 树的节点分配内存。因此，space complexity 为 O(n)，其中 n 是已遍历的流式整数的总数。

方法：使用最小堆和最大堆

概念是使用最小堆和最大堆来保存下半部分和上半部分元素的。Java 中的最小堆和最大堆可以通过 PriorityQueue 来实现。解决问题需要以下步骤。

算法

步骤 1：创建两个堆：一个用于最大堆，用于在任何给定时间维护下半部分的元素；另一个用于最小堆，用于维护上半部分的元素。

步骤 2：将中位数的值初始化为 0。

步骤 3：对于每个当前读取的元素，将其插入最小堆或最大堆，并根据以下条件计算中位数

如果最大堆的大小大于最小堆的大小，并且该元素不大于前一个中位数，则从最大堆的顶部移除该元素并将其放入最小堆，然后将新元素放入最大堆。否则，将新元素放入最小堆。将当前中位数计算为最小堆和最大堆顶部元素的总和除以 2。
如果最大堆的大小小于最小堆的大小，并且该元素大于前一个中位数，则从最小堆的顶部移除该元素并将其放入最大堆，然后将新元素放入最小堆。否则，将新元素放入最大堆。将当前中位数计算为最小堆和最大堆顶部元素的总和除以 2。
如果两个堆的大小相同，则检查当前元素是否小于前一个中位数。如果是，则将当前元素插入最大堆，最大堆顶部的元素就是我们当前的中位数。如果不是，则将当前元素插入最小堆，最小堆顶部的元素就是我们当前的中位数。

文件名：DisplayLeafBST1.java

// import statements required in the program
import java.util.PriorityQueue;
import java.util.Collections;

public class RunningIntegerStream 
{

// Method that displays the median of running or stream integers
public void displayMedian(int inputArr[], int s)
{

float median = inputArr[0];

// max heap for keeping the smaller half elements 
PriorityQueue<Integer> smallerPQ = new PriorityQueue<>
(Collections.reverseOrder());

// minimum heap for keeping the greater half of elements 
PriorityQueue<Integer> greaterPQ = new PriorityQueue<>();

smallerPQ.add(inputArr[0]);
System.out.println("Median after reading element " + inputArr[0] + " is: " + inputArr[0]);

// one by one traversing elements of the stream 
// At any given time, we try to balance the heaps and 
// at most difference in their sizes is 1. If heaps are 
// balanced, then the median is the average of 
// the minHeapRight.top() and the maxHeapLeft.top() 
// If the heaps are unbalanced, then the median is defined 
// as the element at the top of heap of the greater size 
for(int j = 1; j < s; j++)
{
int size1 = smallerPQ.size();
int size2 = greaterPQ.size();
int y = inputArr[j];

// case 1 (the left-side heap has the more number of elements) 
if(size1 > size2)
{
if(y < median)
{
greaterPQ.add(smallerPQ.remove());
smallerPQ.add(y);
}
else
greaterPQ.add(y);
median = (float)(smallerPQ.peek() + greaterPQ.peek())/2f;
}

// case 2 (both heaps are balanced) 
else if(size1 == size2)
{
if(y < median)
{
smallerPQ.add(y);
median = (float)smallerPQ.peek();
}
else
{
greaterPQ.add(y);
median = (float)greaterPQ.peek();
}
}

// case 3 (the right side heap has the more elements) 
else
{
if(y > median)
{
smallerPQ.add(greaterPQ.remove());
greaterPQ.add(y);
}
else
smallerPQ.add(y);
median = (float)(smallerPQ.peek() + greaterPQ.peek()) / 2f;

}
System.out.print( "Median after reading { ");
for(int i = 0; i < j; i++)
{
System.out.print(inputArr[i] + " ");
}
System.out.println( "} elements is " + median );
}

}


// main method
public static void main (String[] argvs) 
{
// creating an object of the class RunningIntegerStream
RunningIntegerStream obj = new RunningIntegerStream();
int inputArr[] = { 17, 11, 15, 13, 10, 12, 18, 19, 1, 16, 14, 20 };
int s = inputArr.length;

// invoking the method displayMedian
obj.displayMedian(inputArr, s);
}
}

输出

Median after reading element 17 is: 17
Median after reading { 17 } elements is 14.0
Median after reading { 17 11 } elements is 15.0
Median after reading { 17 11 15 } elements is 14.0
Median after reading { 17 11 15 13 } elements is 13.0
Median after reading { 17 11 15 13 10 } elements is 12.5
Median after reading { 17 11 15 13 10 12 } elements is 13.0
Median after reading { 17 11 15 13 10 12 18 } elements is 14.0
Median after reading { 17 11 15 13 10 12 18 19 } elements is 13.0
Median after reading { 17 11 15 13 10 12 18 19 1 } elements is 14.0
Median after reading { 17 11 15 13 10 12 18 19 1 16 } elements is 14.0
Median after reading { 17 11 15 13 10 12 18 19 1 16 14 } elements is 14.5

复杂度分析：程序的 time complexity 和 space complexity 与上一个程序相同。

下一主题Java 中的箭头运算符

← 上一个下一个 →

Java 中流式运行整数的中位数

方法：使用插入排序

方法：使用 AVL 树

方法：使用最小堆和最大堆

算法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中流式运行整数的中位数

方法：使用插入排序

方法：使用 AVL 树

方法：使用最小堆和最大堆

算法

相关帖子

Icon interface Java

Java Servlets 和 CGI 的区别

Rust vs. Java

如何在 Java 中使对象可序列化

Java 中 LongConsumer 接口及示例

Read CSV File in Java

Find Total Numbers with No Repeated Digits in A Range in Java

Java 中的排列系数

如何在 Java 中返回二维数组

Java String.valueOf() 方法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器