1.一个整形数组里除了一个数字外，其余数字都出现了2次，如何找出这个数？

1.1 双重循环法

顾名思义，我们可以使用双重循环，找出那个唯一出现一次的数字

public class Test {
    public static void main(String[] args) {
        int [] arr = new int[]{1,1,2,3,3,4,4,2,5};
        System.out.println(num(arr));
    }

    private static int num(int[] arr) {
        for(int i = 0 ; i < arr.length ;i++){
            int count = 0;
            for(int j = 0 ; j < arr.length;j++){
                if(arr[i] == arr[j] && i!=j){
                    count++;
                }
            }
            if(count == 0){
                return arr[i];
            }
        }
        return -1;
    }
}

这种方法时间复杂度为 O(n²)

1.2 先排序后遍历

我们可以先对数组排序，然后从第一个数字开始遍历，比较两个相邻的数，从而找出这个只出现1次的数字

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int [] arr = new int[]{1,1,2,3,3,4,4,2,5};
        System.out.println(num(arr));
    }

    private static int num(int[] arr) {
        Arrays.sort(arr);
        int i;
        for(i = 0; i < arr.length-1; i= i+2){
            if(arr[i] != arr[i+1]){
                return arr[i];
            }
        }
        if(i < arr.length){
            return arr[i];
        }else{
            return -1;
        }
    }
}

时间复杂度为：0(nlogn)

1.3 异或

任何一个数字异或自己都等于0
将整个数字从头都尾依次异或，那么那些出现两次的数字全部哎异或中会被抵消掉，最终结果刚好是这个只出现1次的数字

public class Test1 {
    public static void main(String[] args) {
        int [] arr = new int[]{1,1,2,3,4,4,2};
        System.out.println(num(arr));
    }

    private static int num(int[] arr) {
        int temp = arr[0];
        for(int i = 1; i < arr.length; i++){
           temp ^= arr[i];
        }
        return temp;
    }
}

时间复杂度为0(n)

2.一个整形数组里除了一个数字外，其余数字都出现了3次，如何找出这个数？

2.1 双重循环法

public class Test {
    public static void main(String[] args) {
        int [] arr = new int[]{1,2,1,2,4,2,4,4,1,3};
        System.out.println(num(arr));
    }

    private static int num(int[] arr) {
        for(int i = 0 ; i < arr.length ;i++){
            int count = 0;
            for(int j = 0 ; j < arr.length;j++){
                if(arr[i] == arr[j] && i!=j){
                    count++;
                }
            }
            if(count == 0){
                return arr[i];
            }
        }
        return -1;
    }
}

时间复杂度：o(n²)

2.2 先排序后遍历

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int [] arr = new int[]{1,2,1,2,4,2,4,4,1,3,3,3};
        System.out.println(num(arr));
    }

    private static int num(int[] arr) {
        Arrays.sort(arr);
        int i;
        for(i = 0; i < arr.length-2; i= i+3){
            if(arr[i] != arr[i+1] || arr[i] != arr[i+2]
                    || arr[i+2] != arr[i+1]){
                return arr[i];
            }
        }
        if(i < arr.length){
            return arr[i];
        }else{
            return -1;
        }
    }
}

时间复杂度：o(n)

2.3 最佳算法

上述的异或运算只适合于其他数字出现的次数为偶数的情况，如果其他数字出现的次数为奇数，上述方法将不再使用。

如果数组中的所有数都出现3次，那么这个数组中的所有数对应的二进制数中，各个位上的1出现的次数总和均可以被3整除

假如数组中有如下元素：{1,1,1,2,2,2} 它们对应的二进制为{01,01,01,10,10,10}显然这个数组中的所有数字对应的二进制数中第0位有3个1，第1位有3个1，假设出现一次的这个数为a，那么去掉a后其他所有数字对应的二进制数的每个位置出现1的个数总和均为3的倍数
那么我们的实现步骤为：

1. 计算数组中所有数字对应的二进制数各个位置的和，即就是计算数组中所有数字对应的二进制数各个位置出现1的次数
2. 若某一位上的数不能被3整除，则证明目标数字的这一位肯定为1

public class Main {
    public static void main(String[] args) {
        int [] arr = new int[]{1,2,1,2,4,2,4,4,1,3};
        System.out.println(findOnce(arr,3));
    }

    private static int findOnce(int[] arr, int k) {
        int n = arr.length;
        int []bitCount = new int[32];
        //计算数组中所有数据对应的二进制数各个位上出现1的次数总和
        for(int i = 0 ; i < n;i++){
            for(int j = 0 ; j < 32;j++){
                bitCount[j] += ( ( (arr[i]>>j) ) & 1 );
            }
        }
        //若某位上的结果不能被整除，则肯定目标数字在这一位
        int appearOne = 0;
        for(int i = 0 ; i < 32;i++){
            if(bitCount[i] % k != 0){
                appearOne += (1<<i);
            }
        }
        return appearOne;
    }
}

这种方法不仅适用于求解其他数字出现次数为奇数的情况，也适用于求解其他数字出现次数为偶数的情况!!!

最后

以上就是想人陪心锁为你收集整理的一个整形数组里除了一个数字外，其余数字都出现了2次，那么如何找出这个数？ 以及 一个整形数组里除了一个数字外，其余数字都出现了3次，那么如何找出这个数？1.一个整形数组里除了一个数字外，其余数字都出现了2次，如何找出这个数？2.一个整形数组里除了一个数字外，其余数字都出现了3次，如何找出这个数？的全部内容，希望文章能够帮你解决一个整形数组里除了一个数字外，其余数字都出现了2次，那么如何找出这个数？ 以及 一个整形数组里除了一个数字外，其余数字都出现了3次，那么如何找出这个数？1.一个整形数组里除了一个数字外，其余数字都出现了2次，如何找出这个数？2.一个整形数组里除了一个数字外，其余数字都出现了3次，如何找出这个数？所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。