数据结构与算法--数组中出一次的数字

ゝ一世哀愁。 2022-10-10 13:57 5阅读 0赞

#### 数组中出现一次的数字 ####

*  题目：一个整型数组里面除了一个数字以外，其他数字都出现了两次。找出这个出现一次的数字，时间复杂度O(n)，空间复杂度O(1)
 *  如上题中最简单的方法就是一次循环统计，之后在循环判断出值出现一次的数字，但是空间复杂度会达到O(n)达不到题目中的要求，最直观的方法往往不是我们需要找的最优解
 *  题目中强调了只有一个数字出现了一次，其他都是2次，强调的1次和2次肯定会是有用的条件，我在之前的文章：[数据结构与算法–位运算][Link 1]中有详细解释了异或相关操作以及应用，相同的两个数据异或得到的永远是0
 *  我们可以利用异或逐个去对每个数据进行操作，得到最终的数据就是我们需要的独立出现的数据，
 *  如上分析有如下代码：

public static int findOne(int[] array){ 
            if(array == null){ 
                return 0;
            }
            int resultInt = 0;
            for (int i = 0; i < array.length; i++) { 
                resultInt ^= array[i];
            }
            return resultInt;
        }

*  以上实现我们用一次遍历得到结果，时间复杂度O(n)，空间复杂度O(1)

#### 变种题型，如果有两个不同的数，求这两个 ####

*  以上题型中我们用异或的方式找出了一个不同的数据，那能不能用相同的的方法解决两个的情况。
 *  分析：
    
     *  还是逐个异或，我们得到的比如是两个不同数据异或的结果
     *  如果我们能将这个数组拆分开，并且让两个不同的数据分布在两个不同的数组中
     *  如果做到如上这点，我们可以套用以上的方案去解题，假设不同数据分别是n， m
     *  假设我们异或得到的数据是k， 异或的定义，相同位异或得到0，不同位异或得到1
     *  那么我们在数据 k的二进制位中任意找一位，我们找第一位是1 位置标记为position
     *  我们遍历 数组，判断所有数据中 position 位置是否为1，是1 则放入第一个数组，是二则放入
     *  此时n， m的position 为必然是不同的，这个时候我们就可以将n， m区分开来到两个数组
     *  同理，相同的两个数据z，z’，相同的position位必然是一样，那么必然在一个数组中
     *  至此我们将两个数据拆分开
     *  经过如上分析有如下代码：

/** * @author liaojiamin * @Date:Created in 17:59 2021/6/28 */
    public class FindShowOnceInArray { 
    
        public static void main(String[] args) { 
            int[] array = new int[]{ 2,998,3,77,3,2,5,5};
            int result = 0;
            for (int i = 0; i < array.length; i++) { 
                result ^= array[i];
            }
            int[] resultTemp = findOnceNum(array);
            System.out.println(resultTemp.length+ ": "+ resultTemp[0] + ": "+ resultTemp[1]);
        }
    
        /** * 一个数组中有两个数单个存在，其他的都是成对存在，找出这两个数 * */
        public static int[] findOnceNum(int[] array){ 
            if(array == null || array.length <= 2){ 
                return array;
            }
            int resultInt = 0;
            for (int i = 0; i < array.length; i++) { 
                resultInt^=array[i];
            }
            System.out.println(resultInt);
            int position = checkoutPosition(resultInt);
            System.out.println(position);
            int[] arrayIsone = new int[array.length];
            int positionOne = 0;
            int[] arrayNotOne = new int[array.length];
            int positionNotOne = 0;
            int positionNum = 1;
            positionNum <<=position;
            System.out.println(positionNum);
            for (int i = 0; i < array.length; i++) { 
                if((array[i]&positionNum) == positionNum){ 
                    arrayIsone[positionOne] = array[i];
                    positionOne++;
                }else { 
                    arrayNotOne[positionNotOne] = array[i];
                    positionNotOne++;
                }
            }
            int[] resultTemp = new int[2];
            int oneResult = 0;
            int twoResult = 0;
            for (int i = 0; i < positionOne; i++) { 
                oneResult^=arrayIsone[i];
            }
            resultTemp[0]=oneResult;
            for (int i = 0; i < positionNotOne; i++) { 
                twoResult^=arrayNotOne[i];
            }
            resultTemp[1] = twoResult;
            return resultTemp;
        }
    
    
    
        /** * 找到目标数据二进制数第一位为1 的位置 * */
        public static int checkoutPosition(int resultInt){ 
            int position = 0;
            for(;resultInt > 0; resultInt>>=1){ 
                if((resultInt&1) == 1){ 
                    return position;
                }
                position++;
            }
            return position;
    
        }
    }

*  如上实现中利用异或运算的特性来筛选出不同的两个数据，并且利用 与 运算俩排查 第n位上的数据是否为1，用2次循环得到结果，时间复杂度为O(n)，但是空间复杂度也是O(n)
 *  我们可以对他进行如下改造，不存储直接运算得出结果，如下

/** * O(n) 空间复杂度 * 一个数组中有两个数单个存在，其他的都是成对存在，找出这两个数 * */
        public static int[] findOnceNumON(int[] array){ 
            if(array == null || array.length <= 2){ 
                return array;
            }
            int resultInt = 0;
            for (int i = 0; i < array.length; i++) { 
                resultInt^=array[i];
            }
            System.out.println(resultInt);
            int position = checkoutPosition(resultInt);
            System.out.println(position);
            int positionOne = 0;
            int positionNotOne = 0;
            int positionNum = 1;
            positionNum <<=position;
            System.out.println(positionNum);
            for (int i = 0; i < array.length; i++) { 
                if((array[i]&positionNum) == positionNum){ 
                    positionOne^=array[i];
                }else { 
                    positionNotOne^=array[i];
                }
            }
            int[] resultTemp = new int[2];
            resultTemp[0]= positionOne;
            resultTemp[1] = positionNotOne;
            return resultTemp;
        }

*  如上实现，我们得到时间复杂度O(n)，空间复杂度O(n)的实现方案

[上一篇：数据结构与算法–二叉树的深度问题][Link 2]  
[下一篇：数据结构与算法–有序数组中找出和为s的两个数字][s]

[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/114941988
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/118216064
[s]: https://blog.csdn.net/liaojiamin0102/article/details/118342126