正确答案是:
class Solution {
public:
int findRepeatNumber(vector& nums) {
int i=0;
while (i
我的是:
swap(nums[i],nums[nums[i]]);
if(nums[i]==nums[nums[i]]) return nums[i];
这里不能先swap(nums[i],nums[nums[i]]);再判断if(nums[i]==nums[nums[i]]) return nums[i],否则只要测试用例中有0,总会在某一时刻执行到nums[0]=0
此时表达式if(nums[0]==nums[nums[0]]) return nums[i]的条件一定为真,就会返回0(=nums[0]=nums[nums[0]])
因此只要测试用例中有0就一定会出错.
错误的原因主要是:每次执行++i后,就应该先判断这个数在之前是否出现过,而不是先交换.
对于测试用例[2, 3, 1, 0, 2, 5, 3]
前者:
[2, 3, 1, 0, 2, 5, 3]->1,2不同->swap:[1, 3, 2, 0, 2, 5, 3]->1,3不同->[3, 1, 2, 0, 2, 5, 3]->3,0不同->[0, 1, 2, 3, 2, 5, 3]->进入continue循环,++i->i=4时,nums[4]==nums[nums[4]]->return 2
后者:
[2, 3, 1, 0, 2, 5, 3]->swap:[1, 3, 2, 0, 2, 5, 3]->1,3不同->[3, 1, 2, 0, 2, 5, 3]->3,0不同->[0, 1, 2, 3, 2, 5, 3]->swap(nums[0],nums[nums[0]])(nums[0]==nums[nums[0]]!!!)->if(nums[0]==nums[nums[0]])为真->return nums[0] (return 0)
也就是说当测试用例中含有0时,0最终一定在索引为0的位置,并且i一直会等于0,这样下一次的swap操作,就是自身和自身swap,就像上面写的那样,接着下一条语句就是if(nums[i]==nums[nums[i]])一定为真,返回0.
if (i==nums[i])
{
++i;
continue;
}
这个代码块的意思就是为了避免这种情况.因此swap之后应该执行++i操作消除自己等于自己的可能,然后再判断if(nums[i]==nums[nums[i]])
然而使用我的方法时,只要测试用例含有0,紧跟着的是if(nums[i]==nums[nums[i]])一定为真,所以++i这个语句块永远都走不进去
但若测试用例不含0,这两种方法并无差异,因为两者的目的都是把数字和放到对应的索引位置.
为什么测试用例中没0就没事呢?:
if (i==nums[i])
{
++i;
continue;
}
因为当测试用例没有0时,上面的语句块其实没有存在的必要.
因为nums[0]这个位置也永远是非0的其他数字,i==nums[i]一定是假,此时
swap(nums[i],nums[nums[i]]);
if(nums[i]==nums[nums[i]]) return nums[i];
和
if(nums[i]==nums[nums[i]]) return nums[i];
swap(nums[i],nums[nums[i]]);
从结果来讲确实没有什么区别.但依然不严谨
考虑输入为[3, 3, 1, 2]
显然我的方法会走捷径.
因此即使题目限制输入没有0,也依然应该使用先if再swap的方案.
最后的思考&总结:
输入里的每个数字就像火箭,每个火箭都有自己对应的发射器(索引),当某个发射器上有两个火箭时,就说明重复了.
初始化,i=0这个位置作为第一个发射器,把自己位置上的这些数字发射到他们所属的索引位置.同时那个索引位置处的火箭会被替换到i=0这个发射器.
而swap就是发射&自动替换这对操作,需要注意的是发射器(索引)发射的火箭(数字)数字相同是不允许的.因为这时的if(nums[i]==nums[nums[i]]) return nums[i];一定成立,失去了判断意义.
对于测试样例无0的情况:
i=0这个发射器没有属于自己的发射物(即只有0这个索引,但输入没有0这个数字),因此永远都不会出现发射器和火箭一样的情况(i != nums[i] forever!!! 也就是说++i语句块从始至终不会执行)
若测试用例中存在重复的数字,那么索引为这个重复数字的接收器就会接收到两个数字相同的火箭,并且一定是i=0这个发射器发射来的.
对于测试样例有0的情况:
i=0处的发射器有自己的火箭,一旦经过某个swap后,i=0的发射器和数字为0的火箭匹配上,就需要立即移到i=1处的发射器,否则i=0发射的火箭就会回到自己的发射器(if(nums[i]==nums[nums[i]]) return nums[i];)一定成立,导致误判.
换句话讲,发射器只能接收到其他发射器发射来的火箭
而++i就是为了防止发射器发射出去的火箭又回到自己这种情况的.因此每次发射(swap)后,就得看看自动替换来的新火箭是不是和该发射器数字一样,如果是(if (i==nums[i]))就得紧跟着执行++i语句.
出错的原因:
如果用我的方法++i -> swap -> if,swap后没有判断发射器发射的火箭时候会回到自身,那么只要输入中有数字0,return 索引为0处的火箭(数字),即0.因此正确方法应该是swap -> ++i -> if
但即使输入没0,我的方法也不太好,如上面提到的[3, 3, 1, 2],不再赘述.
剑指offer04 二维数组的查找
class Solution {
public:
bool findNumberIn2DArray(vector>& matrix, int target) {
int i=matrix.size()-1;
int j=0;
while(i>=0 && j<=matrix[0].size()-1){
if(targetmatrix[i][j])
++j;
else
return true;
}
return false;
}
};
错1:给i赋值的时候忘了减1
错2:while条件判断的后半部分应该是j
