算法通关村第三关-黄金挑战数组问题

本文主要是介绍算法通关村第三关-黄金挑战数组问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大家好我是苏麟 , 今天带来第三关黄金挑战关 .

今天有几道小题

数组中只出现一次的元素

题目 :

LCR 070. 有序数组中的单一元素 : 

有序数组中只出现一次的元素

分析  :

因为这里肯定会出现一个单个数字 , 所以不考虑都是双数的存在 .

第一种方法 : 最直接的方法就是遍历比较 , 让nums[i]和nums[i+1]比较 , 如果相同就比较下一组 , 如果 i=nums.length就说明 最后一个元素是单个的 , -1不用管 , 因为不到-1就返回了.

第二种方法 : 二分法 : 

//0 1 2 3 4 5 6 7 8 9 10 元素下标

//1 1 2 2 3 3 4 5 5 6 6  元素值

在没有单个元素之前判断方式nums[i] == nums[i+1] , 在有了单个元素之后之前那只种就比较不了改用 nums[i] -- nums[i - 1] ,所以判断mid % 2 == 0很重要 , 之后就开始收缩 , 逐步完成搜索 .

第三种方法 : 位运算

0 ^ 0 = 0
a ^ a = 0
a ^ b ^ a = b

解析 : 

LeetCode

普通 

class Solution {public int singleNonDuplicate(int[] nums) {int i = 0;for( i = 0; i< nums.length - 1 ;i++){if(nums[i] == nums[i + 1]){i++;}else{return nums[i];}}if(i == nums.length - 1){return nums[i];}//由于题目特性 不会走到这里return -1;  }
}

二分法

//二分法
class Solution {public int singleNonDuplicate(int[] nums) {//0 1 2 3 4 5 6//1 1 2 3 3 4 4int left  = 0 ;int right = nums.length - 1;while(left < right){int mid = left + (right - left) / 2 ;if(mid % 2 == 0){if(nums[mid] == nums[mid + 1]){left = mid + 1;}else{right = mid;}}else{if(nums[mid] == nums[mid-1]){left = mid + 1;}else{right = mid;}}}return nums[left];}
}

 位运算

class Solution {public int singleNonDuplicate(int[] nums) {int flag = 0;for(int x : nums){flag ^= x;}return flag;}
}

这篇关于算法通关村第三关-黄金挑战数组问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---