Discuss / Java / 找出有序中的缺值——先复制一个从start到end的列表 A ，判断A中的元素是否与list内的元素相等，相等则删除列表A中的元素，最后剩余的元素就是要找的缺值
Back

找出有序中的缺值——先复制一个从start到end的列表 A ，判断A中的元素是否与list内的元素相等，相等则删除列表A中的元素，最后剩余的元素就是要找的缺值

Topic source

Little虔

#1 Created at ... [Delete] [Delete and Lock User] 
import java.util.*;
// 给定一组连续的整数，例如：10，11，12，……，20，但其中缺失一个数字，试找出缺失的数字：
public class Practice {
    public static void main(String[] args) {
        // 构造从start到end的序列：
        final int start = 10;
        final int end = 20;
        List<Integer> list = new ArrayList<>();
        for (int i = start; i <= end; i++) {
            list.add(i);
        }
        // 随机删除List中的一个元素:
        int removed = list.remove((int) (Math.random() * list.size()));
        System.out.println(removed);
        int found = findMissingNumber(start, end, list);
        System.out.println(list.toString());
        System.out.println("missing number: " + found);
        System.out.println(removed == found ? "测试成功" : "测试失败");
    }
    
    static int findMissingNumber(int start, int end, List<Integer> list) {
        List<Integer> arry = new ArrayList<>();
        for (int i = start; i <= end; i++) {
            arry.add(i);
        }
        for (int i=0; i < arry.size(); i++) {
            for (Integer j:list) {
                if (arry.get(i) == j) {
                    arry.remove(i);        
                }
            }
            
        }
        return arry.get(0);
    }

}

Little虔

#2 Created at ... [Delete] [Delete and Lock User]

该方法同样适用于无序找值。但其中

for (int i=0; i < arry.size(); i++)

是廖老师不推荐的写法，也用到了get方法获取列表中的值，get(int)方法只有ArrayList的实现是高效的，换成LinkedList后，索引越大，访问速度越慢。

Little虔

#3 Created at ... [Delete] [Delete and Lock User]

对于无序查找，会出现索引超出范围的情况，修复代码如下：

for (int i=0; i < len; i++) {
            for (Integer j:list) {
                if (arry.get(i) == j) {
                    arry.remove(i);
                    // 修改处
                    //由于列表移除元素后，列表长度变化，索引会有超出范围的情况，需要重置长度、索引下标
                    len = arry.size();
                    i = 0;
                }
            }
            
        }
  • 1

Reply