欢迎大家关注我的以下主页，尤其是今日头条！！！谢谢🙏🙏🙏
csdn：雷园的csdn博客
个人博客：雷园的个人博客
简书：雷园的简书
今日头条：来自底层程序员的仰望
前言
- 最近准备把算法慢慢的捡起来，所以准备经常来更新一道算法题目，难度自然是由简入难，所以同学们可以每天都来看看小编的更新。
- 北京的生活总是匆忙的，希望在北京的活着将要来北京生活的伙伴们，不要被这无情的生活淹没。最起码抽出一些时间，来做一些自己喜欢的事情。
题目：
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: [3,3,7,7,10,11,11]
输出: 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
解题思路
-
这道题目的用暴力求解是相当的简单，但是我们看到题目的注意事项。要求我们应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
-
看到这里就看到了难度，如何去控制时间以及空间。
-
我们既不可以使用空间去换取时间，也不可以用时间去换取空间。那应该如何操作呢？
-
我们现来看一下常用的两个查找方法的时间复杂度：
-
由此可见我们想要将查找的时间控制在O(log n)，我们可以使用折半查询。
-
那使用折半查询如何验证元素是否唯一呢？由题可以看到给定一个只包含整数的有序数组，所以我们只需要判断某一元素的前驱和后继是否有与自身相同。
代码实现
class Solution {
private static int ans; // 定义结果
/**
* 递归方法，获取单一元素
**/
public static void getSingleNonDuplicate(int[] nums,int low,int heigh){
// 折半查询
if(low<=heigh){
int mid=(low+heigh)/2;
// 判断元素的前驱和后继是否与自身相同
if((mid>0&&nums[mid-1]==nums[mid])||(mid+1<nums.length&&nums[mid+1]==nums[mid])){
// 查询左边
getSingleNonDuplicate(nums,low,mid-1);
// 查询右边
getSingleNonDuplicate(nums,mid+1,heigh);
}else
ans=nums[mid]; // 给结果元素赋值
}
}
public static int singleNonDuplicate(int[] nums) {
getSingleNonDuplicate(nums,0,nums.length-1);
return ans;
}
}
最后说两句
- 所有的题目都有很多种解法，我的一定不是最好的，甚至可以说是比较低端的解法，希望大牛们多多指教！！！
- 如果朋友们对算法、编程有很大兴趣的话，可以私信我，大家一同探讨；相互学习、共同进步。
- 朋友们如果对这道题目有更好的解法，希望可以在评论中指出，让大家一起讨论学习。
- 最后感谢大家的阅读以及关注，谢谢大家！！！
