今日算法之_1杀人算法_2数字数组找缺少数字

偏执的太偏执、 2022-04-15 02:56 174阅读 0赞

### 1、杀人算法    ###

#### 解释：把犯人围城一圈，每次杀掉第七个，又从第八个开始杀掉第七个，直到剩下最后一个 ####

#### 代码目录（domo0001KillPerson） ####

package com.hlj.arith.domo0001KillPerson;
    
    import lombok.Data;
    import lombok.experimental.Accessors;
    import org.junit.jupiter.api.Test;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /** * 1、 杀人算法 : * 把犯人围城一圈，每次杀掉第七个，又从第八个开始杀掉第七个，直到剩下最后一个 * * @Author HealerJean * @Date 2018/10/10 下午1:37. */
    public class TestMain { 
    
        @Data
        @Accessors(chain = true)
        public class Person { 
            private String name ;
            private Integer sort;
        }
    
    
        @Test
        public void start(){ 
    
            Integer n = 20 ;
    
            //1、配置人数，名字以及顺序
            List<Person> persons = setPersonBySystem(n);
            prinnt(persons);
    
            //2、开始杀人,中间使用了递归
            killPerson(n,persons);
    
        }
    
    
        /** * 1、系统输入 人数，设置PerSon的数据 * @return */
        public List<Person> setPersonBySystem(Integer n){ 
            List persons = new ArrayList<>();
            for(Integer i = 1 ; i<=n ; i++){ 
                persons.add(new Person().setName("healerjean"+i).setSort(i));
            }
            return  persons ;
        }
    
        /** * 杀人之后重新排序 * @param n * @param persons * @return */
        public List<Person> killPerson(Integer n, List<Person> persons){ 
    
                List<Person>  personEnd =  persons.subList(7, persons.size()); //从第8为开始取数据
                List<Person> personStart = persons.subList(0, 6); //从第一位开始取数据
    
                personEnd.addAll(personStart);//将前面的加到后面去
                prinnt(personEnd);
                if(personEnd.size()>6){  //表示索引最小也得是7
                    killPerson(n, personEnd);
                }
                return  personEnd ;
    
        }
    
        public void prinnt(List<Person> person){ 
            person.stream().forEach(s->{ 
                System.out.print(s.getSort()+",");
            });
            System.out.println();
        }
    
    
    }

### 2、给定一个 1-100 的整数数组，请找到其中缺少的数字。 ###

#### 代码目录 (domo0002MissingNumberInArray) ####

#### 知识点 ####

*  BitSet的应用场景 海量数据去重、排序、压缩存储
 *  BitSet的基本操作 and（与）、or（或）、xor（异或）
 *

package com.hlj.arith.domo0002MissingNumberInArray;
    
    import org.junit.jupiter.api.Test;
    
    import java.util.Arrays;
    import java.util.BitSet;
    
    /**
     * @Desc: 给定一个 1-100 的整数数组，请找到其中缺少的数字。
     *
     * 解答：
     *  BitSet的应用场景  海量数据去重、排序、压缩存储
     *  BitSet的基本操作   and（与）、or（或）、xor（异或）
     *
     *
     * @Author HealerJean
     * @Date 2018/10/10  下午2:18.
     */
    public class TestMain {
    
    
        @Test
        public void start(){
            // 丢失3个数据
            printMissingNumber(new int[]{1, 2, 3, 4, 6, 9, 8}, 10);
    
    
            // Only one missing number in array
            int[] iArray = new int[]{1, 2, 3, 5};
            int missing = getMissingNumber(iArray, 5);
    
        }
    
        /**
         * BitSet   海量数据去重、排序、压缩存储
         * @param numbers
         * @param count
         */
        private  void printMissingNumber(int[] numbers, int count) {
            int missingCount = count - numbers.length;
            BitSet bitSet = new BitSet(count);
    
            for (int number : numbers) {
                bitSet.set(number - 1); //数据是从1开头的，这里是获取下标索引
            }
    
            System.out.println("一共有"+count+"个数据：目前数组为"+Arrays.toString(numbers));
    
            int lastMissingIndex = 0;
            for (int i = 0; i < missingCount; i++) {
                lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);//返回下个清零位的索引，（即，下一个零位），从由startIndex指定的索引开始
                System.out.println(++lastMissingIndex);
            }
    
        }
    
        /**
         * 如果是数组中之缺少一个，则根据1到100的累加和 减去 目前的数组的累加和
         * @param numbers
         * @param totalCount
         * @return
         */
        private  int getMissingNumber(int[] numbers, int totalCount) {
            int expectedSum = totalCount * ((totalCount + 1) / 2);
            int actualSum = 0;
            for (int i : numbers) {
                actualSum += i;
            }
            System.out.println("一共有"+totalCount+"个数据：目前数组为"+Arrays.toString(numbers));
            System.out.println(expectedSum - actualSum);
    
            return expectedSum - actualSum;
        }
    
    }

![ContactAuthor][]

[ContactAuthor]: /images/20220415/6e6b27560dea41be826244799dbf5971.png