HackerRank中Find Missing & Repeating Number列表实现运行错误排查

题目说明 #

给定一个包含N个整数的只读集合（元素范围[1,N]），其中存在一个重复两次的整数A，以及一个缺失的整数B，需要找出A和B并返回。

• 输入格式：第一行输入整数n，第二行输入n个整数
• 样例输入：

  3
  3 1 3
  

• 样例输出：3 2

错误代码 #

public static List<Integer> find_missing(List<Integer> arr) {
            int i;
        // Repeating number
        for (i = 0; i < arr.size(); i++) {
            int abs_val = Math.abs(arr.get(i));
            if (arr.get(abs_val - 1) > 0)
                arr.get(abs_val - 1) = -arr.get(abs_val - 1);
            else
                return abs_val;
        }
 //Missing number
        for (i = 0; i < arr.size(); i++) {
            if (arr.get(i) > 0)
                return (i + 1);
        }
}

错误原因分析 #

• List元素修改方式错误：arr.get()仅返回元素的引用/值，无法直接通过对返回值赋值来修改集合内的元素，必须使用set()方法完成修改。
• 返回类型不匹配：方法声明返回List<Integer>，但代码中直接返回单个整数，不符合方法签名要求。

修正后的代码 #

import java.util.ArrayList;
import java.util.List;

public static List<Integer> find_missing(List<Integer> arr) {
    List<Integer> result = new ArrayList<>();
    int repeating = -1;
    
    // 定位重复数
    for (int i = 0; i < arr.size(); i++) {
        int absVal = Math.abs(arr.get(i));
        if (arr.get(absVal - 1) > 0) {
            arr.set(absVal - 1, -arr.get(absVal - 1));
        } else {
            repeating = absVal;
        }
    }
    
    // 定位缺失数
    int missing = -1;
    for (int i = 0; i < arr.size(); i++) {
        if (arr.get(i) > 0) {
            missing = i + 1;
            break;
        }
    }
    
    result.add(repeating);
    result.add(missing);
    return result;
}

内容的提问来源于stack exchange，提问作者The Programmer