为何移除有序数组重复项的代码仅在注释break后生效?
问题原因分析
你的break语句位置是导致代码出错的核心问题:
因为if条件后面没有加大括号,所以只有found = 1;是if的执行代码,break语句是独立在if之外的。这意味着内层循环每次只执行j=0的迭代就会立刻break退出,根本没机会检查j从1到i-1的其他位置。
举个实际例子:假设数组是[1,2,2],当i=2(对应元素2)时,内层循环j=0时nums[2]≠nums[0],found保持0,然后直接执行break退出内层循环——此时代码错误地认为这个2是第一次出现,会将其写入数组,导致重复项没有被过滤。
当你注释掉break后,内层循环会完整遍历j从0到i-1的所有位置,只要前面有任何一个元素和当前nums[i]相等,found就会被设为1,这样就能正确判断当前元素是否为重复项,代码也就正常工作了。
代码优化建议
你的代码还有可以简化和高效化的空间:
- 内层循环无需遍历整个
nums.length,只需要遍历到j < i即可,因为我们只需要检查当前元素之前的位置,能减少大量无效循环。 read变量和i完全同步递增,完全可以用nums[i]代替nums[read],去掉多余的read变量。- 找到重复项后可以立即break内层循环(这次要把break放在
if的大括号里),避免不必要的遍历。
优化后的代码示例:
class Solution { public int removeDuplicates(int[] nums) { int write = 0; for (int i = 0; i < nums.length; i++) { int found = 0; // 仅遍历当前元素之前的位置 for (int j = 0; j < i; j++) { if (nums[i] == nums[j]) { found = 1; // 找到重复项就立即退出内层循环 break; } } if (found == 0) { nums[write] = nums[i]; write++; } } return write; } }
更高效的双指针解法(针对有序数组特性)
因为题目明确是有序数组,重复元素必然相邻,所以可以用双指针法把时间复杂度降到O(n),无需嵌套循环:
class Solution { public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int write = 1; for (int read = 1; read < nums.length; read++) { // 只需要和前一个元素比较即可判断是否重复 if (nums[read] != nums[read - 1]) { nums[write] = nums[read]; write++; } } return write; } }
内容的提问来源于stack exchange,提问作者Bereket Mezgebu
相关产品推荐
相关产品推荐

