算法练习·找出数组中的单身狗

算法练习·找出数组中的单身狗

问题:从以下数组中找出只出现一次的数字

入门级:循环遍历数组中的每个数字出现的次数

 public static void main(String[] args) {

        Integer[] arr = {1,2,1,2,6,8,6,9,8};

        int singleNumber = -1;
        for (int i = 0; i < arr.length; i++) {
            if(counter(arr,arr[i]) == 1){
                singleNumber = arr[i];
                break;
            }
        }
        System.out.println(singleNumber);
    }

    /**
     * 计算元素在数组中出现的次数
     */
    private static int counter(Integer[] arr,int number){

        int count = 0;
        for (Integer integer : arr) {
            if (integer == number) {
                count++;
            }
        }
        return count;
    }

时间复杂度:O(n2)

高级:异或操作(自反性)

  • 交换律:a ^ b = b ^ a
  • 结合律:a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c; d = a ^ b ^ c 可以推出 a = d ^ b ^ c
  • 自反性:a ^ b ^ a = b

点我查看更详细的介绍

java实现

    public static void main(String[] args) {

        Integer[] arr = {1,2,1,2,6,8,6,9,8};

        int singleNumber = arr[0];
        for (int i = 1; i < arr.length; i++) {
            singleNumber = singleNumber ^ arr[i];
        }

        System.out.println(singleNumber);
    }

时间复杂度:O(n)

# 算法  java 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×