Leetcode -- Merge Sorted Array (很诡异的问题)

#include <iostream>
using namespace std;

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int i = m-1;
        int j = n-1;
        int k = m+n-1;

        for (; i>=0 && j>=0; k--) {
            if (B[j] > A) {
                A[k] = B[j];
                j--;
            }
            else {
                A[k] = A;
                i--;
            }
        }
        while (j >= 0) {
            A[k] = B[j];
            k--;
            j--;
        }
        //cout << m << ", " << n << endl;               
        //for (int z=0; z<m+n; z++) cout << A[z] << endl;
    }
};

int main()
{

    int A[] = {1,1,2,2,3,3};
    int B[] = {1,1,2,2,3};
    int m = 6;   
    int n = 5;

    Solution s;
    s.merge(A, m, B, n);
    cout << m << " " << n << endl;
    for (int z=0; z<m+n; z++) cout << A[z] << endl;

    return 0;
}
===============输入结果=============================
3 3
1
1
1
1
2
2
===============END===============================
问题是程序里面没有任何地方修改m, n的值，系统修改了m,n的值
将代码中的
    int m = 6;   
    int n = 5;
改为
    const int m = 6;   
    const int n = 5;

===============输入结果=============================
6 5
1
1
1
1
2
2
2
2
3
3
3
===============END===============================
结果是正确的了，但是代码没有修改m,n的值，所以我觉得没必要设置const.
烦请各位大神帮忙看下。

我试了一下，不加const运行结果也是对的，但运行完毕时出现“Stack around the variable was corrupted” 错误，看了一下楼主的代码，合并的结果是都存到数组A里了，但数组A一开始并没有足够的空间容纳两个数组的内容，所以其实是有越界访问，解决方案要么把A的容量设得足够大，要么动态分配一块新的内存足以容纳A和B的所有元素

有人在leetcode上回答了一下:
https://oj.leetcode.com/discuss/5799/python-wa-input-1-output-0-expected-1
"A is not actually [], though it claims to be. In order to be able to return nothing, A needs space for all of B (so long as you can't modify the length of an array). Because of this, in this case, A is [0], with m=0, while the input with A=[0], m=1 would be written as A=[0] as well, so long as B=[],n=0.

The judge for this problem knows how many elements are required, so it looks in its array, which gets passed to A, and checks the first m+n slots. Since m=0,n=1, it checks the first slot, which is the least number in your array, the [0]. Instead of using len(A) or len(B), use m and n instead."
意思就是A其实本来就有足够的空间容纳m + n的元素. m只是用于告之developer当前A数组中只有前m个元素有意义. 同理n之于B.

希望这个有所帮助.

ralf 发表于 2014-7-26 03:14
我试了一下，不加const运行结果也是对的，但运行完毕时出现“Stack around the variable was corrupted”  ...

多谢解答，是创建的数组不够大，越界了。好弱智，还看了好久。

xiaozhang79 发表于 2014-7-26 04:06
有人在leetcode上回答了一下:
https://oj.leetcode.com/discuss/5799/python-wa-input-1-output-0-expecte ...

多谢多谢，太疏忽了。

你的m和n是紧接着你的数组A和B分配的。。所以你A越界的话。会把m的值改变。如果你把n和m声明为const的，可以就会分配到global的区域。

Linzertorte 发表于 2014-7-26 05:05
你的m和n是紧接着你的数组A和B分配的。。所以你A越界的话。会把m的值改变。如果你把n和m声明为const的，可 ...

原来如此，学到了，多谢大神指点，没想到这么一个低级的错误会生成这样的结果。还看了我半天的时间，实在是发现不了就po上来了，丢人啊。