admin管理员组文章数量:1026373
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int* asd;
bool flag1 = false, flag2 = false;
asd = malloc(sizeof(int) * (nums1Size + nums2Size));
int br1 = 0, br2 = 0;
for (int i = 0; i < (nums1Size + nums2Size); i++) {
if (flag1) {
asd[i] = nums2[br2];
br2++;
} else if (flag2) {
asd[i] = nums1[br1];
br1++;
} else if (nums1[br1] >= nums2[br2]) {
asd[i] = nums2[br2];
br2++;
if (br2 == nums2Size) {
br2--;
flag2 = true;
}
} else {
asd[i] = nums1[br1];
br1++;
if (br1 == nums1Size) {
br1--;
flag1 = true;
}
}
printf("%d\n", asd[i]);
}
if ((nums1Size + nums2Size) % 2 == 0) {
double a = (asd[(nums1Size + nums2Size) / 2] + asd[(nums1Size + nums2Size) / 2 - 1]);
return a / 2;
} else {
return asd[(nums1Size + nums2Size) / 2];
}
}
Test casses are good, but it wont submit.
When I try to submit the code, I get the following error:
==23==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000001f0
...
SUMMARY: AddressSanitizer: heap-buffer-overflow solution.c:16 in findMedianSortedArrays
...
I suspect the issue is caused by br1 or br2 exceeding the bounds of their respective arrays (nums1 or nums2). I tried adding boundary checks for br1 and br2, but I still couldn't resolve the issue. I also verified the size of the dynamically allocated array asd (it should be nums1Size + nums2Size), and it seems correct. Is there a bug in the logic of merging the arrays or accessing their elements? How can I ensure I don't access out-of-bounds memory for nums1 or nums2? Is there a more efficient way to solve this problem?
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int* asd;
bool flag1 = false, flag2 = false;
asd = malloc(sizeof(int) * (nums1Size + nums2Size));
int br1 = 0, br2 = 0;
for (int i = 0; i < (nums1Size + nums2Size); i++) {
if (flag1) {
asd[i] = nums2[br2];
br2++;
} else if (flag2) {
asd[i] = nums1[br1];
br1++;
} else if (nums1[br1] >= nums2[br2]) {
asd[i] = nums2[br2];
br2++;
if (br2 == nums2Size) {
br2--;
flag2 = true;
}
} else {
asd[i] = nums1[br1];
br1++;
if (br1 == nums1Size) {
br1--;
flag1 = true;
}
}
printf("%d\n", asd[i]);
}
if ((nums1Size + nums2Size) % 2 == 0) {
double a = (asd[(nums1Size + nums2Size) / 2] + asd[(nums1Size + nums2Size) / 2 - 1]);
return a / 2;
} else {
return asd[(nums1Size + nums2Size) / 2];
}
}
Test casses are good, but it wont submit.
When I try to submit the code, I get the following error:
==23==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000001f0
...
SUMMARY: AddressSanitizer: heap-buffer-overflow solution.c:16 in findMedianSortedArrays
...
I suspect the issue is caused by br1 or br2 exceeding the bounds of their respective arrays (nums1 or nums2). I tried adding boundary checks for br1 and br2, but I still couldn't resolve the issue. I also verified the size of the dynamically allocated array asd (it should be nums1Size + nums2Size), and it seems correct. Is there a bug in the logic of merging the arrays or accessing their elements? How can I ensure I don't access out-of-bounds memory for nums1 or nums2? Is there a more efficient way to solve this problem?
Share Improve this question edited Nov 17, 2024 at 1:04 Ted Lyngmo 119k7 gold badges84 silver badges136 bronze badges asked Nov 17, 2024 at 0:24 golub001golub001 113 bronze badges 2 |2 Answers
Reset to default 2} else if (nums1[br1] >= nums2[br2]) {
In this line, you will access an array out of bounds if its empty.
You are also leaking memory since you do not free(asd) before returning. You don't even need to do any allocation at all to find the middle element(s). Just loop to the midpoint and store the current low and the previous value (in case of an even amount of elements).
Example:
#include <math.h>
#include <stddef.h>
double findMedianSortedArrays(int* nums1, size_t nums1Size, int* nums2,
size_t nums2Size) {
size_t totSize = nums1Size + nums2Size;
if (totSize == 0) return NAN; // not a number
size_t mid = totSize / 2 + 1;
int prev, curr = 0; // previous number and current number
// Loop for as long as there are numbers left in both arrays
// and we've not reached the midpoint
for (; nums1Size && nums2Size && mid; --mid) {
prev = curr; // store the previous number
// store the smallest number in curr and step the
// pointer in the selected array and decrease its size:
if (*nums1 < *nums2) {
curr = *nums1;
++nums1;
--nums1Size;
} else {
curr = *nums2;
++nums2;
--nums2Size;
}
}
if (mid--) {
// We haven't reach the midpoint so one of the arrays must have
// more elements. Fast forward "mid" steps in that array:
if (nums1Size) {
nums1 += mid;
if (mid) prev = nums1[-1];
else prev = curr;
curr = *nums1;
} else {
nums2 += mid;
if (mid) prev = nums2[-1];
else prev = curr;
curr = *nums2;
}
}
if (totSize % 2 == 0) return (prev + curr) / 2.0;
return curr;
}
Demo
You simply didn't check if there's a test case where one of the arrays was empty. If one of them was empty, you submitted code would simply check for the first index of that empty array (since you've initiated br1 and br2 to 0). Here's a fixed code that includes this case:
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int* asd;
bool flag1 = false, flag2 = false;
asd = malloc(sizeof(int) * (nums1Size + nums2Size));
int br1 = 0, br2 = 0;
if (nums2Size == 0){
for(int i = 0;i<nums1Size;i++){
asd[i] = nums1[i];
}
} else if (nums1Size == 0){
for(int i = 0;i<nums2Size;i++){
asd[i] = nums2[i];
}
}else {
for (int i = 0; i < (nums1Size + nums2Size); i++) {
if (flag1) {
asd[i] = nums2[br2];
br2++;
} else if (flag2) {
asd[i] = nums1[br1];
br1++;
} else if (nums1[br1] >= nums2[br2]) { //this is line 23
asd[i] = nums2[br2];
br2++;
if (br2 == nums2Size) {
br2--;
flag2 = true;
}
} else {
asd[i] = nums1[br1];
br1++;
if (br1 == nums1Size) {
br1--;
flag1 = true;
}
}
printf("%d\n", asd[i]);
}
}
if ((nums1Size + nums2Size) % 2 == 0) {
double a = (asd[(nums1Size + nums2Size) / 2] + asd[(nums1Size + nums2Size) / 2 - 1]);
return a / 2;
} else {
return asd[(nums1Size + nums2Size) / 2];
}
}
You simply check if one of arrays was already empty. If so, you return the non-empty list, otherwise you start merging. Submit the code and see yourself.
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int* asd;
bool flag1 = false, flag2 = false;
asd = malloc(sizeof(int) * (nums1Size + nums2Size));
int br1 = 0, br2 = 0;
for (int i = 0; i < (nums1Size + nums2Size); i++) {
if (flag1) {
asd[i] = nums2[br2];
br2++;
} else if (flag2) {
asd[i] = nums1[br1];
br1++;
} else if (nums1[br1] >= nums2[br2]) {
asd[i] = nums2[br2];
br2++;
if (br2 == nums2Size) {
br2--;
flag2 = true;
}
} else {
asd[i] = nums1[br1];
br1++;
if (br1 == nums1Size) {
br1--;
flag1 = true;
}
}
printf("%d\n", asd[i]);
}
if ((nums1Size + nums2Size) % 2 == 0) {
double a = (asd[(nums1Size + nums2Size) / 2] + asd[(nums1Size + nums2Size) / 2 - 1]);
return a / 2;
} else {
return asd[(nums1Size + nums2Size) / 2];
}
}
Test casses are good, but it wont submit.
When I try to submit the code, I get the following error:
==23==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000001f0
...
SUMMARY: AddressSanitizer: heap-buffer-overflow solution.c:16 in findMedianSortedArrays
...
I suspect the issue is caused by br1 or br2 exceeding the bounds of their respective arrays (nums1 or nums2). I tried adding boundary checks for br1 and br2, but I still couldn't resolve the issue. I also verified the size of the dynamically allocated array asd (it should be nums1Size + nums2Size), and it seems correct. Is there a bug in the logic of merging the arrays or accessing their elements? How can I ensure I don't access out-of-bounds memory for nums1 or nums2? Is there a more efficient way to solve this problem?
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int* asd;
bool flag1 = false, flag2 = false;
asd = malloc(sizeof(int) * (nums1Size + nums2Size));
int br1 = 0, br2 = 0;
for (int i = 0; i < (nums1Size + nums2Size); i++) {
if (flag1) {
asd[i] = nums2[br2];
br2++;
} else if (flag2) {
asd[i] = nums1[br1];
br1++;
} else if (nums1[br1] >= nums2[br2]) {
asd[i] = nums2[br2];
br2++;
if (br2 == nums2Size) {
br2--;
flag2 = true;
}
} else {
asd[i] = nums1[br1];
br1++;
if (br1 == nums1Size) {
br1--;
flag1 = true;
}
}
printf("%d\n", asd[i]);
}
if ((nums1Size + nums2Size) % 2 == 0) {
double a = (asd[(nums1Size + nums2Size) / 2] + asd[(nums1Size + nums2Size) / 2 - 1]);
return a / 2;
} else {
return asd[(nums1Size + nums2Size) / 2];
}
}
Test casses are good, but it wont submit.
When I try to submit the code, I get the following error:
==23==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000001f0
...
SUMMARY: AddressSanitizer: heap-buffer-overflow solution.c:16 in findMedianSortedArrays
...
I suspect the issue is caused by br1 or br2 exceeding the bounds of their respective arrays (nums1 or nums2). I tried adding boundary checks for br1 and br2, but I still couldn't resolve the issue. I also verified the size of the dynamically allocated array asd (it should be nums1Size + nums2Size), and it seems correct. Is there a bug in the logic of merging the arrays or accessing their elements? How can I ensure I don't access out-of-bounds memory for nums1 or nums2? Is there a more efficient way to solve this problem?
Share Improve this question edited Nov 17, 2024 at 1:04 Ted Lyngmo 119k7 gold badges84 silver badges136 bronze badges asked Nov 17, 2024 at 0:24 golub001golub001 113 bronze badges 2-
Unrelated: You don't need to do any allocation to find the middle element(s). Even if you do use an allocation, you don't need it to have space for more than
(nums1Size + nums2Size) / 2 + 1elements – Ted Lyngmo Commented Nov 17, 2024 at 2:14 - 1 oh that is a great way of thinking thank you so much. – golub001 Commented Nov 17, 2024 at 12:04
2 Answers
Reset to default 2} else if (nums1[br1] >= nums2[br2]) {
In this line, you will access an array out of bounds if its empty.
You are also leaking memory since you do not free(asd) before returning. You don't even need to do any allocation at all to find the middle element(s). Just loop to the midpoint and store the current low and the previous value (in case of an even amount of elements).
Example:
#include <math.h>
#include <stddef.h>
double findMedianSortedArrays(int* nums1, size_t nums1Size, int* nums2,
size_t nums2Size) {
size_t totSize = nums1Size + nums2Size;
if (totSize == 0) return NAN; // not a number
size_t mid = totSize / 2 + 1;
int prev, curr = 0; // previous number and current number
// Loop for as long as there are numbers left in both arrays
// and we've not reached the midpoint
for (; nums1Size && nums2Size && mid; --mid) {
prev = curr; // store the previous number
// store the smallest number in curr and step the
// pointer in the selected array and decrease its size:
if (*nums1 < *nums2) {
curr = *nums1;
++nums1;
--nums1Size;
} else {
curr = *nums2;
++nums2;
--nums2Size;
}
}
if (mid--) {
// We haven't reach the midpoint so one of the arrays must have
// more elements. Fast forward "mid" steps in that array:
if (nums1Size) {
nums1 += mid;
if (mid) prev = nums1[-1];
else prev = curr;
curr = *nums1;
} else {
nums2 += mid;
if (mid) prev = nums2[-1];
else prev = curr;
curr = *nums2;
}
}
if (totSize % 2 == 0) return (prev + curr) / 2.0;
return curr;
}
Demo
You simply didn't check if there's a test case where one of the arrays was empty. If one of them was empty, you submitted code would simply check for the first index of that empty array (since you've initiated br1 and br2 to 0). Here's a fixed code that includes this case:
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int* asd;
bool flag1 = false, flag2 = false;
asd = malloc(sizeof(int) * (nums1Size + nums2Size));
int br1 = 0, br2 = 0;
if (nums2Size == 0){
for(int i = 0;i<nums1Size;i++){
asd[i] = nums1[i];
}
} else if (nums1Size == 0){
for(int i = 0;i<nums2Size;i++){
asd[i] = nums2[i];
}
}else {
for (int i = 0; i < (nums1Size + nums2Size); i++) {
if (flag1) {
asd[i] = nums2[br2];
br2++;
} else if (flag2) {
asd[i] = nums1[br1];
br1++;
} else if (nums1[br1] >= nums2[br2]) { //this is line 23
asd[i] = nums2[br2];
br2++;
if (br2 == nums2Size) {
br2--;
flag2 = true;
}
} else {
asd[i] = nums1[br1];
br1++;
if (br1 == nums1Size) {
br1--;
flag1 = true;
}
}
printf("%d\n", asd[i]);
}
}
if ((nums1Size + nums2Size) % 2 == 0) {
double a = (asd[(nums1Size + nums2Size) / 2] + asd[(nums1Size + nums2Size) / 2 - 1]);
return a / 2;
} else {
return asd[(nums1Size + nums2Size) / 2];
}
}
You simply check if one of arrays was already empty. If so, you return the non-empty list, otherwise you start merging. Submit the code and see yourself.
本文标签： decodingHeap Buffer Overflow in findMedianSortedArrays Function in C (LeetCode)Stack Overflow
版权声明：本文标题：decoding - Heap Buffer Overflow in findMedianSortedArrays Function in C (LeetCode) - Stack Overflow 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/questions/1745641208a2160758.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
(nums1Size + nums2Size) / 2 + 1elements – Ted Lyngmo Commented Nov 17, 2024 at 2:14