🙊本文目录👍
- 🙊写在前面🙊
- 题目
- 示例
- 提示
- 📝思路📝
- ⭐代码实现⭐
- 运行结果
- 🙊写在最后🙊
🙊写在前面🙊
今天是情人节 不过 这题出的深意让人脑瓜子嗡嗡的，俩俩配对，找单出来的元素，好家伙直接破防，情侣中找单身狗，没想到啊，小丑竟是我自己~
题目
示例
示例1：
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例2:
输入: nums = [3,3,7,7,10,11,11]
输出: 10
提示
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^5
📝思路📝
本题考查知识点
解题思路大致有两种：
- 第一种：直接暴力AC 因为这是一个有序数组，如果从第一组元素（一组元素为2个）开始，如果出现一组元素不相同时 那么二者之间肯定有一个是单身元素。当然也可以采用哈希表计数。
- 第二种：因为本题希望时间复杂度为 logn 那就不能采用暴力的方式了，两两配对，二分查找。
⭐代码实现⭐
暴力AC
class Solution {public int singleNonDuplicate(int[] nums) {int n= nums.length;//俩两凑对子 如果该分组中出现不一致则不是情侣 返回第一个元素for(int i=0;i<n-1;i+=2){if(nums[i] != nums[i+1]){return nums[i];}}//如果遍历到最后一个元素时直接返回这个单身狗return nums[n-1];}
}
二分（情人节 二分法真的好么？）
class Solution {public int singleNonDuplicate(int[] nums) {int left = 0;int right = nums.length-1;int mid ;//直接套模板就是了while(left < right){mid = left + (right - left )/2;if (mid % 2 == 1)mid--;if (nums[mid] == nums[mid+1])left+=2;else {right = mid;}}return nums[left];}
}
运行结果
暴力AC
二分查找
🙊写在最后🙊
2022-2-14今天小付打卡了哦~
美好的日出 美好的山河
都因有你存在 而璀璨 耀眼
本文链接：https://my.lmcjl.com/post/19402.html
展开阅读全文
4 评论