在Java中找出1到n个数字之间的重复数

程序员文章站 2024-03-15 15:28:30

...

给出一个长度为n+1的列表，它的数值范围从1到n，其中一个数字是重复的，你必须找到重复的数字。这个问题非常类似于在数组中查找缺少的数字。在这篇文章中，我将分享一个java程序和算法，以找到1到n个数字之间的重复数字。

算法

1.计算列表中所有数字的总和。

2.计算列表中唯一数的大小n，并使用算术级数公式n*(n+1)/2

3.从第一步减去第二步中所得到的数值，你将得到重复的数字。

Java程序

import java.util.List;
import java.util.ArrayList;
public class DuplicateNumberProgram {
    public static void main(String args[]) {
        // Creating the list 
        List<Integer> numbers = new ArrayList<Integer>();
        // Add numbers from 1 to n
        for(int i=1; i < 40; i++) {
            numbers.add(i);
        }
        // adding duplicate number into the list
        numbers.add(35);
        DuplicateNumberProgram obj = new DuplicateNumberProgram();
        int duplicateNumber = obj.getDuplicateNumber(numbers);
        System.out.println(duplicateNumber);
    }
    
    public int findSum(List<Integer> numbers) {
        int sum =0;
        for(int number : numbers) {
            sum += number;
        }
        return sum;
    }
    
    public int getDuplicateNumber(List<Integer> numbers) {
        int n = numbers.size()-1;
        int total = findSum(numbers);
        int duplicateNum = total - (n * (n+1)/2);
        return duplicateNum;
    }
}