Java 中未排序数组中的第 K 小元素

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

在给定的数组中，任务是找到数组的第 k 小的元素，其中 k 总是小于给定数组的大小。

示例

输入

arr[] = {56, 34, 7, 9, 0, 48, 41, 8}

k = 3

输出: 数组的第 3 小的元素是 8。

输入

arr[] = {90, 87, 30, 9, 12, 41, 13, 80, 67, 70}

k = 4

输出: 数组的第 4 小的元素是 30。

方法：对数组进行排序

这是一种直接的方法。你需要对数组进行排序，然后从左边返回第 K 个元素。

文件名: KthSmallestEle.java

public class KthSmallestEle
{

// method for sorting the array arr
public void sortArr(int arr[])
{
int size = arr.length;

for(int i = 0; i < size; i++)
{
int temp = i;
for(int j = i + 1; j < size; j++)
{
if(arr[temp] > arr[j])
{
temp = j;
}



}


if(temp != i)
{
int t = arr[i];
arr[i] = arr[temp];
arr[temp] = t; 
}
}
}

// find the kth smallest element of the array
public int findKthSmallest(int arr[], int k)
{
sortArr(arr);

// as an array is always a zero indexing
// therefore, the kth smallest element lies
// at the k - 1 index
return arr[k - 1];
}


// main method
public static void main(String argvs[])
{

// creating an object of the class KthSmallestEle
KthSmallestEle obj = new KthSmallestEle();

int arr[] = {56, 34, 7, 9, 0, 48, 41, 8};

int size = arr.length;
int k = 3;

System.out.println("For the array: ");
for(int i = 0; i < size; i++)
{
System.out.print(arr[i] + " ");
}

int ele = obj.findKthSmallest(arr, k);

System.out.println();
System.out.println("The " + k + "rd smallest element of the array is: " + ele);

System.out.println("\n");

int arr1[] = {90, 87, 30, 9, 12, 41, 13, 80, 67, 70};

size = arr1.length;
k = 4;

System.out.println("For the array: ");
for(int i = 0; i < size; i++)
{
System.out.print(arr1[i] + " ");
}

ele = obj.findKthSmallest(arr1, k);

System.out.println();
System.out.println("The " + k + "th smallest element of the array is: " + ele);

}
}

输出

For the array: 
56 34 7 9 0 48 41 8 
The 3rd smallest element of the array is: 8


For the array: 
90 87 30 9 12 41 13 80 67 70 
The 4th smallest element of the array is: 30

时间复杂度: 上述程序的时间复杂度取决于 sortArr() 方法中实现的排序技术。在我们的例子中，使用的技术是选择排序。因此，上述程序的时间复杂度为 O(n²)，其中 n 是数组中元素的总数。

方法：使用最小堆

也可以使用最小堆来查找数组的第 k 小的元素。

文件名: KthSmallestEle1.java

public class KthSmallestEle1
{

// A class for the minimum heap
class MinimumHeap
{
int[] h; // pointer to array of the elements in heap


// represents the capacity of the minimum heap
int c; 

// the total number of elements present in the min-heap
int heapSize; 

// a method for returning the index of the parent node
int parent(int j) 
{ 
return (j - 1) / 2; 
}

// a method for returning the index of the left node
int left(int j) 
{ 
return ((2 * j ) + 1); 

}

// a method for returning the index of the right node
int right(int j) 
{ 
return ((2 * j ) + 2); 

}

// Returning the minimum
int getMin() 
{ 
return h[0 ]; 

} 

// for replacing the root with the new node y and then heapify()
// the new root
void replaceMax(int y)
{
this.h[0 ] = y;
heapify(0 );
}

// constructor of the class
MinimumHeap(int arr[], int s)
{
heapSize = s;

// storing the array address
h = arr; 
int j = (heapSize - 1 ) / 2;
while (j >= 0)
{
heapify(j );
j = j - 1;
}
}

// Method for removing the maximum element (or the root) from the minimum heap
int extractMin()
{
if (heapSize == 0)
{
return Integer.MAX_VALUE;
}

// Storing the maximum value.
int r = h[0];

// If there are more than 1 item, move the last item to the root
// and call heapify.
if (heapSize > 1)
{
h[0] = h[heapSize - 1];
heapify(0);
}
heapSize = heapSize - 1;
return r;
}

// A recursive method for heapifying the subtree with the root at the given index
// The method is assuming that the subtrees are heapified already
void heapify(int j)
{
int lt = left(j);
int rt = right(j);
int minimum = j;
if (lt < heapSize && h[lt] < h[j])
{
minimum = lt;
}
if (rt < heapSize && h[rt ] < h[minimum ] )
{
minimum = rt;
}
if (minimum != j )
{
int t = h[j ];
h[j] = h[minimum ];
h[minimum ] = t;
heapify(minimum );
}
}
};

// Function to return k'th largest element in a given array
public int findKthSmallest(int a[], int s, int k)
{

// Building the heap of the first k elements: in the O(k ) time
// creating an object of the class MinimumHeap
MinimumHeap mHeap = new MinimumHeap(a, s );

// If the current element 
// is smaller than the root, then replace the root with the current element
for (int j = 0; j < k - 1; j++)
{
mHeap.extractMin();
}

// Returning the root
return mHeap.getMin();
}

// main method for testing the above methods
public static void main(String[] args)
{
// creating an object of the class KthSmallestEle1
KthSmallestEle1 obj = new KthSmallestEle1();

int arr[] = {56, 34, 7, 9, 0, 48, 41, 8 };

int size = arr.length;
int k = 3;

System.out.println("For the array: " );
for(int i = 0; i < size; i++)
{
System.out.print(arr[i] + " " );
}

int ele = obj.findKthSmallest(arr, size, k );

System.out.println();
System.out.println("The " + k + "rd smallest element of the array is: " + ele );

System.out.println("\n" );

int arr1[] = {90, 87, 30, 9, 12, 41, 13, 80, 67, 70 };

size = arr1.length;
k = 4;

System.out.println("For the array: ");
for(int i = 0; i < size; i++)
{
System.out.print(arr1[i] + " ");
}

ele = obj.findKthSmallest(arr1, size, k);

System.out.println();
System.out.println("The " + k + "th smallest element of the array is: " + ele);

}

}

输出

For the array: 
56 34 7 9 0 48 41 8 
The 3rd smallest element of the array is: 8


For the array: 
90 87 30 9 12 41 13 80 67 70 
The 4th smallest element of the array is: 30

时间复杂度: 上述程序的时间复杂度为 O(n + k * log(n))，其中 n 是数组中元素的总数，k 是需要搜索的最小元素的排名。

方法：使用最大堆

也可以使用最大堆来查找数组的第 k 小的元素。观察以下算法。

步骤 1: 使用输入数组的前 k 个元素（a[0], …, a[k - 1]）创建一个最大堆。

步骤 2: 将第 k 个元素之后的每个元素（a[k] 到 a[n - 1]）与最大堆的根元素进行比较。在进行比较时，会发生以下两种情况。

情况 1: 如果当前元素小于最大堆的根元素，则用当前元素替换根元素，并调用 heapify() 方法重新排列最大堆中的元素。

情况 2: 如果当前元素大于根元素，则忽略该元素。

文件名: KthSmallestEle2.java

public class KthSmallestEle2
{

// A class for the maximum heap
class MaximumHeap
{
int[] h; // pointer to array of the elements in heap


// represents the capacity of the minimum heap
int c; 

// the total number of elements present in the min-heap
int heapSize; 

// a method for returning the index of the parent node
int parent(int j) 
{ 
return (j - 1) / 2; 
}

// a method for returning the index of the left node
int left(int j) 
{ 
return ((2 * j ) + 1); 

}

// a method for returning the index of the right node
int right(int j) 
{ 
return ((2 * j ) + 2); 

}

// Returning the maximum
int getMax() 
{ 
return h[0 ]; 

} 

// for replacing the root with the new node y and then heapify()
// the new root
void replaceMax(int y)
{
this.h[0 ] = y;
heapify(0 );
}

// constructor of the class
MaximumHeap(int arr[], int s)
{
heapSize = s;

// storing the array address
h = arr; 
int j = (heapSize - 1 ) / 2;
while (j >= 0)
{
heapify(j );
j = j - 1;
}
}

// Method for removing the maximum element (or the root) from the minimum heap
int extractMax()
{
if (heapSize == 0)
{
return Integer.MAX_VALUE;
}

// Storing the maximum value.
int r = h[0];

// If there are more than 1 item, move the last item to the root
// and call heapify.
if (heapSize > 1)
{
h[0] = h[heapSize - 1];
heapify(0);
}
heapSize = heapSize - 1;
return r;
}


// A recursive method for heapifying the subtree with the root at the given index
// The method is assuming that the subtrees are heapified already
void heapify(int j)
{
int lt = left(j);
int rt = right(j);
int maximum = j;
if (lt < heapSize && h[lt] > h[j])
{
maximum = lt;
}
if (rt < heapSize && h[rt ] > h[maximum ] )
{
maximum = rt;
}
if (maximum != j )
{
int t = h[j ];
h[j] = h[maximum ];
h[maximum ] = t;
heapify(maximum );
}
}
};

// method to return k'th largest element in a given array
public int findKthSmallest(int a[], int s, int k)
{

// Building the heap of the first k elements: in the O(k ) time
// creating an object of the class MaximumHeap
MaximumHeap mHeap = new MaximumHeap(a, k );

// Processing the s - k elements. If the current element 
// is smaller than the root, then replace the root with the current element

for (int j = k; j < s; j++)
{
if (a[j] < mHeap.getMax())
{
mHeap.replaceMax(a[j]);
}
}

// Returning the root
return mHeap.getMax();
}

// main method for testing the above methods
public static void main(String[] args)
{
// creating an object of the class KthSmallestEle2
KthSmallestEle2 obj = new KthSmallestEle2();

int arr[] = {56, 34, 7, 9, 0, 48, 41, 8 };

int size = arr.length;
int k = 3;

System.out.println("For the array: " );
for(int i = 0; i < size; i++)
{
System.out.print(arr[i] + " " );
}

int ele = obj.findKthSmallest(arr, size, k );

System.out.println();
System.out.println("The " + k + "rd smallest element of the array is: " + ele );

System.out.println("\n" );

int arr1[] = {90, 87, 30, 9, 12, 41, 13, 80, 67, 70 };

size = arr1.length;
k = 4;

System.out.println("For the array: ");
for(int i = 0; i < size; i++)
{
System.out.print(arr1[i] + " ");
}

ele = obj.findKthSmallest(arr1, size, k);

System.out.println();
System.out.println("The " + k + "th smallest element of the array is: " + ele);

}

}

输出

For the array: 
56 34 7 9 0 48 41 8 
The 3rd smallest element of the array is: 8


For the array: 
90 87 30 9 12 41 13 80 67 70 
The 4th smallest element of the array is: 30

时间复杂度: 步骤 1 的时间复杂度为 O(k)，步骤 2 的时间复杂度为 O(n - k) * log(k)。因此，上述程序的时间复杂度为 O(k + (n - k) * log(k))，其中 n 是数组中元素的总数，k 是需要搜索的最小元素的排名。

方法：使用快速排序

在快速排序中，我们选择一个枢轴元素，然后将其放置到正确的位置。枢轴元素会将数组划分为两个未排序的子数组。在此方法中，我们不会执行完整的快速排序。实际上，我们将在枢轴元素成为给定数组的第 k 小元素时停止。

文件名: KthSmallestEle3.java

public class KthSmallestEle3
{
// It is the standard process of partition of the QuickSort Algorithm
// It takes the last element as the pivot element
// and moves all of the smaller elements to the left of
// it and the greater elements to the right of it
public int partition(int[] a, int l, int e)
{
int y = a[e]; 
int j = l;
for (int i = l; i <= e - 1; i++) 
{
if (a[i] <= y) 
{
// Swapping a[j] and a[i]
int temp = a[j];
a[j] = a[i];
a[i] = temp;

j = j + 1;
}
}

// Swapping a[j] and a[r]
int temp = a[j];
a[j] = a[e];
a[e] = temp;

return j;
}

// This method returns the k'th smallest 
// element in the a[l...r] using the QuickSort algorithm.
// We assume that all of the elements in the a[] are unique
public int findKthSmallest(int[] a, int s, int e, int k)
{
// If k is smaller as compared to the number of 
// elements in the array
if (k > 0 && k <= e - s + 1) 
{
// Partitioning the array a[] around the last
// element and retrieve the position of the pivot
// element in the sorted array
int position = partition(a, s, e);

// If the position is the same as k
if (position - s == k - 1)
{
return a[position];
}

// If the position is more, then recur for
// the left subarray
if (position - s > k - 1)
{
return findKthSmallest(a, s, position - 1, k);
}

// Else recurring for the right subarray
return findKthSmallest(a, position + 1, e, k - position + s - 1);
}

// If k is more than the total number of elements
// present in the array
return Integer.MAX_VALUE;
}

// main method for testing the above methods
public static void main(String[] argvs)
{
// creating an object of the class KthSmallestEle3
KthSmallestEle3 obj = new KthSmallestEle3();

int arr[] = {56, 34, 7, 9, 0, 48, 41, 8 };

int size = arr.length;
int k = 3;

System.out.println("For the array: " );
for(int i = 0; i < size; i++)
{
System.out.print(arr[i] + " " );
}

int ele = obj.findKthSmallest(arr, 0, size - 1, k );

System.out.println();
System.out.println("The " + k + "rd smallest element of the array is: " + ele );

System.out.println("\n" );

int arr1[] = {90, 87, 30, 9, 12, 41, 13, 80, 67, 70 };

size = arr1.length;
k = 4;

System.out.println("For the array: ");
for(int i = 0; i < size; i++)
{
System.out.print(arr1[i] + " ");
}

ele = obj.findKthSmallest(arr1, 0, size - 1, k);

System.out.println();
System.out.println("The " + k + "th smallest element of the array is: " + ele);

}

}

输出

For the array: 
56 34 7 9 0 48 41 8 
The 3rd smallest element of the array is: 8


For the array: 
90 87 30 9 12 41 13 80 67 70 
The 4th smallest element of the array is: 30

时间复杂度: 由于在大多数情况下我们不会完成快速排序，因此上述程序的平均时间复杂度为 O(n)。但是，最坏情况下的时间复杂度为 O(n²)，其中 n 是输入数组中元素的总数。

方法：使用有序映射和元素频率

在此方法中，我们将使用一个有序映射，然后将每个元素与其出现频率进行映射。我们已经知道有序映射始终按排序顺序存储数据。因此，我们将不断累加每个元素的出现频率，直到它等于或大于 k，这样就可以从开头找到第 k 个元素，即给定数组的第 k 小的元素。

文件名: KthSmallestEle4.java

// important import statement
import java.util.*;

public class KthSmallestEle4 
{
public int findKthSmallest(TreeMap<Integer, Integer> tm, int k)
{
// counting frequency of element
int freqCount = 0;
for (Map.Entry itr : tm.entrySet())
{

// adding the frequency of occurrences of each element
freqCount = freqCount + (int)itr.getValue();

// if we find the frequency count increases or becomes
// equal to k at any point of time, then return that element
// It is because that element is the kth smallest element.
if (freqCount >= k) 
{
return (int)itr.getKey();
}
}

// control reaching here the value of k is greater than the total element
// present in the given array
return -1; 
}

// main method for testing the above methods
public static void main(String[] argvs)
{
// creating an object of the class KthSmallestEle4
KthSmallestEle4 obj = new KthSmallestEle4();

int arr[] = {56, 34, 7, 9, 0, 48, 41, 8 };

int size = arr.length;
int k = 3;



System.out.println("For the array: " );
for(int i = 0; i < size; i++)
{
System.out.print(arr[i] + " " );
}


TreeMap<Integer, Integer> tm = new TreeMap<Integer, Integer>();
for (int j = 0; j < size; j++) 
{
// mapping each and every element with it's frequency
tm.put(arr[j], tm.getOrDefault(arr[j], 0) + 1);
}

int ele = obj.findKthSmallest(tm, k );

System.out.println();
System.out.println("The " + k + "rd smallest element of the array is: " + ele );

System.out.println("\n" );

int arr1[] = {90, 87, 30, 9, 12, 41, 13, 80, 67, 70 };

size = arr1.length;
k = 4;

System.out.println("For the array: ");
for(int i = 0; i < size; i++)
{
System.out.print(arr1[i] + " ");
}


TreeMap<Integer, Integer> tm1 = new TreeMap<Integer, Integer>();
for (int j = 0; j < size; j++) 
{
// mapping each and every element with it's frequency
tm1.put(arr1[j], tm1.getOrDefault(arr1[j], 0) + 1);
}


ele = obj.findKthSmallest(tm1, k);

System.out.println();
System.out.println("The " + k + "th smallest element of the array is: " + ele);

}

}

输出

For the array: 
56 34 7 9 0 48 41 8 
The 3rd smallest element of the array is: 8


For the array: 
90 87 30 9 12 41 13 80 67 70 
The 4th smallest element of the array is: 30

下一个主题#

← 上一个下一个 →

Java 中未排序数组中的第 K 小元素

方法：对数组进行排序

方法：使用最小堆

方法：使用最大堆

方法：使用快速排序

方法：使用有序映射和元素频率

联系信息

关注我们

教程

面试题

在线编译器

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 中未排序数组中的第 K 小元素

方法：对数组进行排序

方法：使用最小堆

方法：使用最大堆

方法：使用快速排序

方法：使用有序映射和元素频率

相关帖子

如何解决 Java 中的不兼容类型错误

Java Program Number to Word

Nonagonal Number in Java

OOPs MCQ

Java 中的静态数组

Java 中的 OffsetDateTime getOffset() 方法及示例

Java 中的命令模式

如何在 Java 中创建和操作内存映射文件

Java 中所有元素均为偶数或奇数的最大子数组

Java 中的好数程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器