剑指offer-39-数组中出现次数超过一半的数字

女爷i 2021-12-03 22:53 233阅读 0赞

[剑指offer(39) 数组中出现次数超过一半的数字][offer_39_]

package offer;
    
    import org.junit.Test;
    
    /**
     * 采用阵地攻守的思想：
     　　第一个数字作为第一个士兵，守阵地；count = 1；
     　　遇到相同元素，count++;
     　　遇到不相同元素，即为敌人，同归于尽,count--；当遇到count为0的情况，又以新的i值作为守阵地的士兵，继续下去，到最后还留在阵地上的士兵，有可能是主元素。
     　　再加一次循环，记录这个士兵的个数看是否大于数组一般即可。
     * @author kankan
     * @creater 2019-07-17 22:57
     */
    //题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例
    //如输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字2在数组中
    //出现了5次，超过数组长度的一半，因此输出2。
    public class MoreThanHalfNumber {
        //方法二
        public int MoreThanHalfNum_Solution(int[] array) {
            if(null == array || array.length <= 0){
                return -1;
            }
            //1.第一个数字作为第一个士兵，守阵地：count=1
            int num = array[0];
            int count = 1;
            for(int i = 1; i <  array.length; i++){
                //2.又以新的i值作为守阵地的士兵
                if(0 == count){
                    num = array[i];
                    count++;
                    //3.遇到相同元素，count++
                }else if(num == array[i]){
                    count++;
                }else{//4.遇到不相同的元素,count--
                    count--;
                }
            }
            if(count > 0){
                int times = 0;
                //计算该数字出现的次数
                for(int i = 0;i < array.length;i++){
                    if(num == array[i]){
                        times++;
                    }
                }
                //该数字超过一半
                if(2*times > array.length){
                    return num;
                }
            }
            return 0;
        }
        //1.功能测试（存在或者不存在超过数组长度一半的数字）
        @Test
        public void testMoreThanHalfNumber(){
            int[] array = {1, 2, 3, 2, 2, 2, 5, 4, 2};
            int moreThanHalfNum_solution = new MoreThanHalfNumber().MoreThanHalfNum_Solution(array);
            System.out.println(moreThanHalfNum_solution);
        }
        //2.特殊测试（1个数字）
        @Test
        public void testMoreThanHalfNumber1(){
            int[] array = {1};
            int moreThanHalfNum_solution = new MoreThanHalfNumber().MoreThanHalfNum_Solution(array);
            System.out.println(moreThanHalfNum_solution);
        }
        //3.特殊测试（null、1个数字）
        @Test
        public void testMoreThanHalfNumber2(){
            int[] array = {};
            int moreThanHalfNum_solution = new MoreThanHalfNumber().MoreThanHalfNum_Solution(array);
            System.out.println(moreThanHalfNum_solution);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 2]

[offer_39_]: https://www.cnblogs.com/yongh/p/9938889.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70]: /images/20211203/db7920b9ee5543fa9dcdd7e648ec9798.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 1]: /images/20211203/739ee692a2924c4fb2f91d37c0fd2b4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 2]: /images/20211203/26bbd944d28a48ea8735a5c9590cf729.png