关于Array的两个小应用

电玩女神 2022-09-24 06:29 182阅读 0赞

写了一个java类，是关于Array的两个小应用。

应用1：

给定一个数组，除了一个数出现1次之外，其余数都出现N(N>=2)次，输出出现一次的那个数。

应用1的核心是findTheOne方法，它有两个参数，第一个参数是要查找的数组，第二个参数是N的大小。

查找规则是：构建一个32位的数组，用来保存所有元素的每一位上的二进制数字之和，然后依次取出32位中各位的数，用此数除以N，如果没有除尽，则判定它是我们要找的那个数的一部分，取其位上的数求和，最终这个和就是我们要找的那个数。

举例说明：\[2，2，3\]，2

1.取到2，(2>>0)&1结果为0;(2>>1)&1结果为1;(2>>3)&1;...(2>>31)&1结果为0

为了方便，我只取4位，因为后面的都是0。

0 0 1 0

0 0 1 1

对这四们求和，结果为：

0 0 3 1

然后取出各这四位上的数，找出不能被2整除的数

y y n n

取出来的是最后两位

3 1

1<<1结果为2，1<<0结果为1，求和结果为3

故最后结果为3。

应用2：

机选一注双色球

有两种方法doubleBall和doubleBall2。

doubleBall核心是在同一个数组内交换，交换到数组前面的就是我们随机的数。这里一定是随机了6次。

doubleBall2核心是为每个元素标记状态，如果已经取了，就继续；没有取就放入红球数组中。这里有一个缺陷就是，可能会随机6次以上。

java代码：

package com.syz.test;
    
    import java.util.Arrays;
    import java.util.Random;
    
    public class ArrayTest {
        public static void main(String[] args) {
            findTheSpecialOne(10, 4);
            doubleBall();
            doubleBall2();
        }
    
        /**
         * 给定一个数组，除了一个数出现1次之外，其余数都出现N(N>=2)次，输出出现一次的那个数。
         * @Title: findTheSpecialOne
         * @param multiSize 一共有几组相同的数字
         * @param groupSize 每组多少个
         * @return: void
         */
        private static void findTheSpecialOne(int multiSize, int groupSize) {
            int arrayLength = multiSize * groupSize + 1;
            System.out.println("arrayLength:" + arrayLength);
            // 构建这样一个数组
            int[] array = buildArray(arrayLength, multiSize, groupSize);
            System.out.println(Arrays.toString(array));
            // 打乱其顺序
            shuffle(array);
            System.out.println(Arrays.toString(array));
            int one = findTheOne(array, groupSize);
            System.out.println(one);
        }
    
        private static int[] buildArray(int arrayLength, int multiSize,
                int groupSize) {
            int[] array = new int[arrayLength];
            int number = 0;
            // +1是为了加上最后一个只出现一次的数字
            int[] randomArray = randomFromPool(arrayLength, multiSize + 1);
            System.out.println(Arrays.toString(randomArray));
            for (int i = 0; i < arrayLength; i++) {
                if (i % groupSize == 0) {
                    number = randomArray[i / groupSize];
                }
                array[i] = number;
            }
            return array;
        }
    
        /**
         * 
         * @Title: randomFromPool
         * @param poolSize 将要构建的数组的大小
         * @param size 将要返回的不同数字的个数
         * @return
         * @return: int[]
         */
        private static int[] randomFromPool(int poolSize, int size) {
            int[] pool = new int[poolSize];
            for (int i = 0; i < poolSize; i++) {
                pool[i] = i;
            }
            int count = 0;
            Random r = new Random();
            for (int i = 0; i < poolSize; i++) {
                if (count == size) {
                    break;
                }
                count++;
                int idx = r.nextInt(poolSize - i);
                int si = idx + i;
                if (i != si) {
                    swap(pool, i, si);
                }
    
            }
            int[] arry = Arrays.copyOf(pool, size);
            return arry;
        }
    
        private static int findTheOne(int[] array, int groupSize) {
            int bitSize = 32;
            int[] bits = new int[bitSize];
            int i = 0;
            int j = 0;
            int len = array.length;
            for (i = 0; i < len; i++) {
                for (j = 0; j < bitSize; j++) {
                    bits[j] += (array[i] >> j) & 1;
                }
            }
            int result = 0;
            for (j = 0; j < bitSize; j++) {
                if (bits[j] % groupSize != 0) {
                    result += 1 << j;
                }
            }
            return result;
        }
    
        private static void shuffle(int[] arry) {
            Random r = new Random();
            int len = arry.length;
            for (int i = 0; i < len; i++) {
                int idx = r.nextInt(len - i);
                int j = idx + i;
                if (i != j) {
                    swap(arry, i, j);
                }
    
            }
        }
    
        private static void swap(int[] arry, int i, int j) {
            int t = arry[i];
            arry[i] = arry[j];
            arry[j] = t;
        }
    
        private static void doubleBall() {
            int redPoolSize = 33;
            int[] redPool = new int[redPoolSize];
            for (int i = 0; i < redPoolSize; i++) {
                redPool[i] = i + 1;
            }
            System.out.println(Arrays.toString(redPool));
            int redNum = 6;
            int[] redBalls = randomFromPool(redPool, redNum);
            System.out.println(Arrays.toString(redBalls));
            Arrays.sort(redBalls);
            System.out.println(Arrays.toString(redBalls));
            redBalls = Arrays.copyOf(redBalls, redNum + 1);
            System.out.println(Arrays.toString(redBalls));
            Random r = new Random();
            redBalls[redNum] = r.nextInt(16) + 1;
            System.out.println(Arrays.toString(redBalls));
        }
    
        private static void doubleBall2() {
            Random r = new Random();
            int redPoolSize = 33;
            int[] redPool = new int[redPoolSize];
            for (int i = 0; i < redPoolSize; i++) {
                redPool[i] = i + 1;
            }
            System.out.println(Arrays.toString(redPool));
            boolean[] redBallStatus = new boolean[redPoolSize];
            int redNum = 6;
            int[] redBalls = new int[redNum];
            int count = 0;
            int c = 0;
            while(true){
                c++;
                int idx = r.nextInt(redPoolSize);
                if (redBallStatus[idx]) {
                    continue;
                }
                redBalls[count++] = redPool[idx];
                redBallStatus[idx] = true;
                if (count == redNum) {
                    break;
                }
            }
            System.out.println("c===" + c);// c有可能大于6
            System.out.println(Arrays.toString(redBalls));
            Arrays.sort(redBalls);
            System.out.println(Arrays.toString(redBalls));
            redBalls = Arrays.copyOf(redBalls, redNum + 1);
            System.out.println(Arrays.toString(redBalls));
            redBalls[redNum] = r.nextInt(16) + 1;
            System.out.println(Arrays.toString(redBalls));
        }
    
        private static int[] randomFromPool(int[] pool, int size) {
            int poolSize = pool.length;
            int count = 0;
            Random r = new Random();
            for (int i = 0; i < poolSize; i++) {
                if (count == size) {
                    break;
                }
                count++;
                int idx = r.nextInt(poolSize - i);
                int si = idx + i;
                if (i != si) {
                    swap(pool, i, si);
                }
    
            }
            int[] arry = Arrays.copyOf(pool, size);
            return arry;
        }
    }