【剑指 Offer 53 - II. 0～n-1中缺失的数字】

落日映苍穹つ 2023-09-26 17:03 38阅读 0赞

package com.example.demomain.demoleetcode.easy;
    
    import java.util.Arrays;
    
    /**
     * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
     *
     * 示例 1:
     *
     * 输入: [0,1,3]
     * 输出: 2
     * 示例 2:
     *
     * 输入: [0,1,2,3,4,5,6,7,9]
     * 输出: 8
     * 限制：
     *
     * 1 <= 数组长度 <= 10000
     * @author Administrator
     */
    public class MissingNumber {
        
        /**
         * 直接遍历
         * @param nums
         * @return
         */
        public static int missingNumber(int[] nums) {
        
            int length = nums.length - 1;
            if (nums[0] != 0) {
        
                return 0;
            }
            for (int i = 0; i <= length; i++) {
        
                if (nums[i] != i) {
        
                    return nums[i] - 1;
                }
            }
            return nums[length] + 1;
        }
    
        /**
         * 排序数组 二分法
         * @param nums
         * @return
         */
        public static int missingNumberBin(int[] nums) {
        
            int left = 0, right = nums.length - 1;
            while (left <= right) {
        
                int middle = (left + right) / 2;
                if (nums[middle] == middle) {
        
                    left = middle + 1;
                } else {
        
                    right = middle - 1;
                }
            }
            return left;
        }
    
        /**
         * 数学 （相加求和 缺的即是差）
         * @param nums
         * @return
         */
        private static int missingNumberMath(int[] nums) {
        
            int n = nums.length + 1;
            int total = n * (n - 1) / 2;
            int arrSum = 0;
            for (int i = 0; i < n - 1; i++) {
        
                arrSum += nums[i];
            }
            return total - arrSum;
        }
    
    
    
        public static void main(String[] args) {
        
            System.out.println(missingNumber(new int[]{
        0, 1, 2, 3, 4, 5, 6}));
            System.out.println(missingNumber(new int[]{
        0, 2, 3, 4, 5, 6}));
            System.out.println(missingNumber(new int[]{
        0, 1, 3, 4, 5, 6}));
           
        }
    
    
    }