有序数组中的单一元素

有序数组中的单一元素

Posted by LY on March 19, 2019

在这里小小推荐下我的个人博客

csdn:雷园的csdn博客

个人博客:雷园的个人博客

简书:雷园的简书

前言

  1. 最近准备把算法慢慢的捡起来,所以准备经常来更新一道算法题目,难度自然是由简入难,所以同学们可以每天都来看看小编的更新。
  2. 北京的生活总是匆忙的,希望在北京的活着将要来北京生活的伙伴们,不要被这无情的生活淹没。最起码抽出一些时间,来做一些自己喜欢的事情。

题目:

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

示例 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)空间复杂度中运行。

解题思路

  1. 这道题目的用暴力求解是相当的简单,但是我们看到题目的注意事项。要求我们应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

  2. 看到这里就看到了难度,如何去控制时间以及空间。

  3. 我们既不可以使用空间去换取时间,也不可以用时间去换取空间。那应该如何操作呢?

  4. 我们现来看一下常用的两个查找方法的时间复杂度:屏幕快照 2019-03-19 下午6.03.48

  5. 由此可见我们想要将查找的时间控制在O(log n),我们可以使用折半查询。

  6. 那使用折半查询如何验证元素是否唯一呢?由题可以看到给定一个只包含整数的有序数组,所以我们只需要判断某一元素的前驱和后继是否有与自身相同。

代码实现

   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;
       }
   }

最后说两句

  1. 所有的题目都有很多种解法,我的一定不是最好的,甚至可以说是比较低端的解法,希望大牛们多多指教!!!
  2. 如果朋友们对算法、编程有很大兴趣的话,可以私信我,大家一同探讨;相互学习、共同进步。
  3. 朋友们如果对这道题目有更好的解法,希望可以在评论中指出,让大家一起讨论学习。
  4. 最后感谢大家的阅读以及关注,谢谢大家!!!