c# - 从两个排序数组中获取前 K 项而不合并它们
问题描述
我试图从两个排序数组中获取最大的 K 元素而不合并它们。我的代码使用分而治之的算法,我试图将两个数组与中间元素分开,然后检查中间的数组是否大于另一个我将数组的末尾移到中间,然后我将 k 减少到中间,我将另一个数组从它的开始移动到中间。
我的问题是大输入,这会导致堆栈溢出异常。我不知道为什么,但我认为这是因为如果中间的减法和数组的长度大于 K,我将数组的开头移到中间的语句,我无法解决它。
任何人都可以帮我一个忙并帮助我吗?
public static int GetKthItem(int[] arr1, int[] arr2, int N, int M, int K,
int start1, int start2, int end1, int end2){
if (end1 + end2 == K)
{
return Math.Max(arr1[0], arr2[0]);
}
if (end1 + end2 + 1 == K)
{
return Math.Min(arr1[0], arr2[0]);
}
if (start1 == end1 && K > 0)
{
K--;
if (K > end2 - start2)
return arr2[start2];
else
return arr2[end2 - K];
}
else if (start2 == end2 && K > 0)
{
K--;
if (K > end1 - start1)
return arr1[start1];
else
return arr1[end1 - K];
}
if (K == 0)
{
return Math.Max(arr1[end1], arr2[end2]);
}
int mid1 = (end1 - start1) / 2;
int mid2 = (end2 - start2) / 2;
if (arr2[mid2] >= arr1[mid1])
{
if (end2 - mid2 <= K)
{
return GetKthItem(arr1, arr2, N, M, (K - (end2 - mid2)), mid1,
start2, end1, mid2);
{
else
{
return GetKthItem(arr1, arr2, N, M, K, mid1, start2, end1, end2);
}
}
else
{
if (end1 - mid1 <= K)
{
return GetKthItem(arr1, arr2, N, M, (K - (end1 - mid1)), start1,
mid2, mid1, end2);
{
else
{
return GetKthItem(arr1, arr2, N, M, K, start1, mid2, end1, end2);
}
}
}
解决方案
好吧,如果两个数组已经排序并且您需要获得最大的 K 个元素。您可以有 2 个指针 P1 和 P2。P1 = 数组 1 的最后一个元素 [已排序将是最后一个元素] P2 = 数组 2 的最后一个元素
然后
result[] -- new result array
index = 0
while(index<k){
if (Arr1[P1] > Arr2[P2]){
result[index] = Arr1[P1]
P1--
} else {
result[index] = Arr2[P2]
P2--
}
index++
}
推荐阅读
- javascript - 将 JavaScript 鼠标事件从一个元素传播到另一个元素?
- spring-boot - 在spring boot中上传网络连接速度慢的文件时出错
- swift - 手动解决 Swift 包依赖项
- swift - 在 NSScrollView 中更改 NSView 的框架最终会产生奇怪的值
- qt5 - 为什么 Qt5 在使用信号时会警告有关 miisng 信号?
- javascript - Qlik 如何导入依赖于其他以太的 JS 库
- android - 是否有任何 Android 通知 setContentTitle 和 setContextText 魔法值?
- java - 如何使用具有使用 java 流的属性的不同对象的列表来创建不同对象的列表
- reactjs - 我想对 usestate 或其他钩子做出反应。实施 60 秒倒计时。如何
- php - LARAVEL 调用未定义的方法 Illuminate\Database\Eloquent\Builder::splice()