一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1944|回复: 6
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
fangl086 发表于 2014-7-26 02:27:24 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 fangl086 于 2014-7-26 02:30 编辑

#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.
烦请各位大神帮忙看下。


评分

1

查看全部评分

ralf 发表于 2014-7-26 03:14:17 | 显示全部楼层
我试了一下,不加const运行结果也是对的,但运行完毕时出现“Stack around the variable was corrupted” 错误,看了一下楼主的代码,合并的结果是都存到数组A里了,但数组A一开始并没有足够的空间容纳两个数组的内容,所以其实是有越界访问,解决方案要么把A的容量设得足够大,要么动态分配一块新的内存足以容纳A和B的所有元素
回复 支持 反对

使用道具 举报

xiaozhang79 发表于 2014-7-26 04:06:21 | 显示全部楼层
本帖最后由 xiaozhang79 于 2014-7-26 04:08 编辑

有人在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.

希望这个有所帮助.
回复 支持 反对

使用道具 举报

 楼主| fangl086 发表于 2014-7-26 05:00:39 | 显示全部楼层
ralf 发表于 2014-7-26 03:14
我试了一下,不加const运行结果也是对的,但运行完毕时出现“Stack around the variable was corrupted”  ...

多谢解答,是创建的数组不够大,越界了。好弱智,还看了好久。
回复 支持 反对

使用道具 举报

 楼主| fangl086 发表于 2014-7-26 05:02:07 | 显示全部楼层
xiaozhang79 发表于 2014-7-26 04:06
有人在leetcode上回答了一下:
https://oj.leetcode.com/discuss/5799/python-wa-input-1-output-0-expecte ...

多谢多谢,太疏忽了。
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2014-7-26 05:05:34 | 显示全部楼层
你的m和n是紧接着你的数组A和B分配的。。所以你A越界的话。会把m的值改变。如果你把n和m声明为const的,可以就会分配到global的区域。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| fangl086 发表于 2014-7-26 05:12:20 | 显示全部楼层
Linzertorte 发表于 2014-7-26 05:05
你的m和n是紧接着你的数组A和B分配的。。所以你A越界的话。会把m的值改变。如果你把n和m声明为const的,可 ...

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 06:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表