Thuật toán tìm số bị trùng trong một dãy số có duy nhất 1 số bị trùng.

Trong bài viết này chúng ta sẽ thảo luật về thuật toán tìm một số trùng trong một dãy số có duy nhất 1 số bị trùng. Đây không phải là một thuật toán tìm kiếm số bị trùng toàn vẹn nhưng nó giúp chúng ta mở rộng được tư duy trong việc tính toán.






Do thuật toán chỉ áp trung được đối với một dãy số có duy nhất 1 số bị trùng và chị trung 1 lần duy nhất, nên tôi thiết lập một dãy số ban đầu như sau:

[ 1 2 3 4 5 4 ]

Như ta thấy trong dãy số này ta thấy số 4 là số bị trúng trong dãy số, và để tìm số bị trùng này này ta có công thức toán như sau:

Số bị trùng = Tổng dãy số - (số lượng dãy số * (số lượng dãy số -1)) / 2)

Áp dụng công thức vào dãy số trên ta có:

Số bị trùng = 19 - (6 * (6-1)) / 2 = 4

Bài toán cũng khá hay phải không ^^? Giờ ta hãy thử áp dụng bài toán vào ngôn ngữ lâp trinh Java.

/**
 * @(#)FindDupNumber.java
 *
 * FindDupNumber application
 *
 * @author developer.bnson@gmail.com
 * @version 1.00 2014/3/9
 */

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

public class FindDupNumber {
   
    public static void main(String[] args) {
        List<Integer> arrNumber = new ArrayList<Integer>();
       
        arrNumber.add(1);
        arrNumber.add(2);
        arrNumber.add(3);
        arrNumber.add(4);
        arrNumber.add(5);
        arrNumber.add(4);

        System.out.println("The duplicate number: " + findDupNumber(arrNumber));
        System.out.println(" \n Copyright © VN-Lives");

    }
   
    public static int getSum(List<Integer> arrNum){
        
        int sum = 0;
       
        for(int tmp : arrNum){
            sum += tmp;
        }
       
        return sum;
    }   
   
    public static int findDupNumber(List<Integer> arrNum){
        
        int sizeArrNum = arrNum.size();
       
        int total = getSum(arrNum);
       
        int dupNumber = total - (sizeArrNum*(sizeArrNum - 1) / 2);
       
        return dupNumber;
    }   
   
}

Kết quả sau khi thực thi chương trình sẽ là:

The duplicate number: 4

Copyright © VN-Lives