LeetCode [剑指 Offer II 070. 排序数组中

LeetCode 剑指 Offer II 070. 排序数组中只出现一次的数字

@TOC

题目描述

 给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例：

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 105

一、解题关键词

有序
出现两次
找到出现一次的数字
满足logn 复杂度

二、解题报告

1.思路分析

1. 因为有序，所以先考虑二分,
2. 二分没有具体的判别标准，所以需要所有元素遍历，累加出现次数
3. 一个循环累加
4. 一个循环判断

2.时间复杂度

3.代码示例

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int len = nums.length;

        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < len; i++){
            map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
        }
        for(int i = 0; i < len; i++){
            if(map.get(nums[i]) == 1){
                return nums[i];
            }
        }
        return -1;

    }
}

4.知识点

三、思考

1.相同题目

540. 有序数组中的单一元素