Getting the top K item from two sorted arrays without combine them
I am trying to get the greatest K element from two sorted arrays without merging them. My code uses a divide and conquer algorithm, I am trying to divide the two arrays from the middle element and after that I check if the array one of the middle is greater than the other I shift the end of the array to the middle and I decrease the k by the middle and I am shifting the other array from it's start to the middle.
My problem is with large inputs, which result in a stack overflow exception. I don't know why but I think it's because the statement where I shifted the start of the array to the middle if the subtraction of the middle and the length of array is greater than K and I can't solve it.
Can anyone do me a favor and help me please?
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);
}
}
}
c# arrays algorithm divide-and-conquer
asked Nov 15 '18 at 23:40
Ayman AdelAyman Adel
11
|
show 2 more comments
I am trying to get the greatest K element from two sorted arrays without merging them. My code uses a divide and conquer algorithm, I am trying to divide the two arrays from the middle element and after that I check if the array one of the middle is greater than the other I shift the end of the array to the middle and I decrease the k by the middle and I am shifting the other array from it's start to the middle.
My problem is with large inputs, which result in a stack overflow exception. I don't know why but I think it's because the statement where I shifted the start of the array to the middle if the subtraction of the middle and the length of array is greater than K and I can't solve it.
Can anyone do me a favor and help me please?
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);
}
}
}
c# arrays algorithm divide-and-conquer
asked Nov 15 '18 at 23:40
Ayman AdelAyman Adel
11
The arrays are pre-sorted?
– Joel Coehoorn
Nov 15 '18 at 23:42
There may also be some insight into the answers to this question softwareengineering.stackexchange.com/q/194646/34408
– Mark Schultheiss
Nov 15 '18 at 23:49
An overflowing stack is one of the consequences of deep recursion. Unless the function is amenable to tail call recursion optimization, it's often better to come up with some sort of iterative equivalent to the recursive algorithm.
– Flydog57
Nov 15 '18 at 23:49
Why did you undo the formatting that removed horizontal scrolling? Now people have to scroll horizontally AND vertically to read it. Normally code should be formatted so no horizontal scrolling is necessary.
– Rufus L
Nov 16 '18 at 0:13
1
You might take a look at the third example here, which implements this in C++
– Rufus L
Nov 16 '18 at 0:21
|
show 2 more comments
I am trying to get the greatest K element from two sorted arrays without merging them. My code uses a divide and conquer algorithm, I am trying to divide the two arrays from the middle element and after that I check if the array one of the middle is greater than the other I shift the end of the array to the middle and I decrease the k by the middle and I am shifting the other array from it's start to the middle.
My problem is with large inputs, which result in a stack overflow exception. I don't know why but I think it's because the statement where I shifted the start of the array to the middle if the subtraction of the middle and the length of array is greater than K and I can't solve it.
Can anyone do me a favor and help me please?
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);
}
}
}
c# arrays algorithm divide-and-conquer
asked Nov 15 '18 at 23:40
Ayman AdelAyman Adel
11
I am trying to get the greatest K element from two sorted arrays without merging them. My code uses a divide and conquer algorithm, I am trying to divide the two arrays from the middle element and after that I check if the array one of the middle is greater than the other I shift the end of the array to the middle and I decrease the k by the middle and I am shifting the other array from it's start to the middle.
My problem is with large inputs, which result in a stack overflow exception. I don't know why but I think it's because the statement where I shifted the start of the array to the middle if the subtraction of the middle and the length of array is greater than K and I can't solve it.
Can anyone do me a favor and help me please?
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);
}
}
}
c# arrays algorithm divide-and-conquer
c# arrays algorithm divide-and-conquer
asked Nov 15 '18 at 23:40
Ayman AdelAyman Adel
11
asked Nov 15 '18 at 23:40
Ayman AdelAyman Adel
11
edited Nov 16 '18 at 0:32
Ayman Adel
asked Nov 15 '18 at 23:40
Ayman AdelAyman Adel
11
asked Nov 15 '18 at 23:40
Ayman AdelAyman Adel
11
asked Nov 15 '18 at 23:40
Ayman AdelAyman Adel
11
11
The arrays are pre-sorted?
– Joel Coehoorn
Nov 15 '18 at 23:42
There may also be some insight into the answers to this question softwareengineering.stackexchange.com/q/194646/34408
– Mark Schultheiss
Nov 15 '18 at 23:49
An overflowing stack is one of the consequences of deep recursion. Unless the function is amenable to tail call recursion optimization, it's often better to come up with some sort of iterative equivalent to the recursive algorithm.
– Flydog57
Nov 15 '18 at 23:49
Why did you undo the formatting that removed horizontal scrolling? Now people have to scroll horizontally AND vertically to read it. Normally code should be formatted so no horizontal scrolling is necessary.
– Rufus L
Nov 16 '18 at 0:13
1
You might take a look at the third example here, which implements this in C++
– Rufus L
Nov 16 '18 at 0:21
|
show 2 more comments
The arrays are pre-sorted?
– Joel Coehoorn
Nov 15 '18 at 23:42
There may also be some insight into the answers to this question softwareengineering.stackexchange.com/q/194646/34408
– Mark Schultheiss
Nov 15 '18 at 23:49
An overflowing stack is one of the consequences of deep recursion. Unless the function is amenable to tail call recursion optimization, it's often better to come up with some sort of iterative equivalent to the recursive algorithm.
– Flydog57
Nov 15 '18 at 23:49
Why did you undo the formatting that removed horizontal scrolling? Now people have to scroll horizontally AND vertically to read it. Normally code should be formatted so no horizontal scrolling is necessary.
– Rufus L
Nov 16 '18 at 0:13
1
You might take a look at the third example here, which implements this in C++
– Rufus L
Nov 16 '18 at 0:21
The arrays are pre-sorted?
– Joel Coehoorn
Nov 15 '18 at 23:42
The arrays are pre-sorted?
– Joel Coehoorn
Nov 15 '18 at 23:42
There may also be some insight into the answers to this question softwareengineering.stackexchange.com/q/194646/34408
– Mark Schultheiss
Nov 15 '18 at 23:49
There may also be some insight into the answers to this question softwareengineering.stackexchange.com/q/194646/34408
– Mark Schultheiss
Nov 15 '18 at 23:49
An overflowing stack is one of the consequences of deep recursion. Unless the function is amenable to tail call recursion optimization, it's often better to come up with some sort of iterative equivalent to the recursive algorithm.
– Flydog57
Nov 15 '18 at 23:49
An overflowing stack is one of the consequences of deep recursion. Unless the function is amenable to tail call recursion optimization, it's often better to come up with some sort of iterative equivalent to the recursive algorithm.
– Flydog57
Nov 15 '18 at 23:49
Why did you undo the formatting that removed horizontal scrolling? Now people have to scroll horizontally AND vertically to read it. Normally code should be formatted so no horizontal scrolling is necessary.
– Rufus L
Nov 16 '18 at 0:13
Why did you undo the formatting that removed horizontal scrolling? Now people have to scroll horizontally AND vertically to read it. Normally code should be formatted so no horizontal scrolling is necessary.
– Rufus L
Nov 16 '18 at 0:13
1
1
You might take a look at the third example here, which implements this in C++
– Rufus L
Nov 16 '18 at 0:21
You might take a look at the third example here, which implements this in C++
– Rufus L
Nov 16 '18 at 0:21
|
show 2 more comments
1 Answer
1
active
oldest
votes
Well if the two arrays are already sorted and you need to get the greatest K elements.
You can have 2 pointers P1 and P2.
P1 = Last element of Array 1 [As already sorted will be last element]
P2 = Last element of Array 2
then
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++
}
answered Nov 16 '18 at 3:49
Ravi ChandakRavi Chandak
114
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53329408%2fgetting-the-top-k-item-from-two-sorted-arrays-without-combine-them%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Well if the two arrays are already sorted and you need to get the greatest K elements.
You can have 2 pointers P1 and P2.
P1 = Last element of Array 1 [As already sorted will be last element]
P2 = Last element of Array 2
then
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++
}
answered Nov 16 '18 at 3:49
Ravi ChandakRavi Chandak
114
add a comment |
Well if the two arrays are already sorted and you need to get the greatest K elements.
You can have 2 pointers P1 and P2.
P1 = Last element of Array 1 [As already sorted will be last element]
P2 = Last element of Array 2
then
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++
}
answered Nov 16 '18 at 3:49
Ravi ChandakRavi Chandak
114
add a comment |
Well if the two arrays are already sorted and you need to get the greatest K elements.
You can have 2 pointers P1 and P2.
P1 = Last element of Array 1 [As already sorted will be last element]
P2 = Last element of Array 2
then
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++
}
answered Nov 16 '18 at 3:49
Ravi ChandakRavi Chandak
114
Well if the two arrays are already sorted and you need to get the greatest K elements.
You can have 2 pointers P1 and P2.
P1 = Last element of Array 1 [As already sorted will be last element]
P2 = Last element of Array 2
then
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++
}
answered Nov 16 '18 at 3:49
Ravi ChandakRavi Chandak
114
answered Nov 16 '18 at 3:49
Ravi ChandakRavi Chandak
114
answered Nov 16 '18 at 3:49
Ravi ChandakRavi Chandak
114
answered Nov 16 '18 at 3:49
Ravi ChandakRavi Chandak
114
114
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53329408%2fgetting-the-top-k-item-from-two-sorted-arrays-without-combine-them%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
The arrays are pre-sorted?
– Joel Coehoorn
Nov 15 '18 at 23:42
There may also be some insight into the answers to this question softwareengineering.stackexchange.com/q/194646/34408
– Mark Schultheiss
Nov 15 '18 at 23:49
An overflowing stack is one of the consequences of deep recursion. Unless the function is amenable to tail call recursion optimization, it's often better to come up with some sort of iterative equivalent to the recursive algorithm.
– Flydog57
Nov 15 '18 at 23:49
Why did you undo the formatting that removed horizontal scrolling? Now people have to scroll horizontally AND vertically to read it. Normally code should be formatted so no horizontal scrolling is necessary.
– Rufus L
Nov 16 '18 at 0:13
1
You might take a look at the third example here, which implements this in C++
– Rufus L
Nov 16 '18 at 0:21