📖本篇内容：leetcode每日一题 540. 有序数组中的单一元素 情人节特别篇 一堆情侣中找单身狗~ 没想到小丑是我自己

📑 文章专栏：leetcode每日一题《打卡日常》

📆 最近更新：2022年2月13日 leetcode每日一题 1189. “气球” 的最大数量 简单的模拟题~

🙊个人简介：一只二本院校在读的大三程序猿，本着注重基础，打卡算法，分享技术作为个人的经验总结性的博文博主，虽然可能有时会犯懒，但是还是会坚持下去的，如果你很喜欢博文的话，建议看下面一行~（疯狂暗示QwQ）

🌇 点赞 👍 收藏 ⭐留言 📝 一键三连 _{关爱程序猿，从你我做起}

🙊本文目录👍

• 🙊写在前面🙊
• 题目
• • 示例
  • 提示
  • 📝思路📝
  • ⭐代码实现⭐
  • 运行结果
• 🙊写在最后🙊

🙊写在前面🙊

今天是情人节 不过 这题出的深意让人脑瓜子嗡嗡的，俩俩配对，找单出来的元素，好家伙直接破防，情侣中找单身狗，没想到啊，小丑竟是我自己~

题目

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

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

示例

示例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今天小付打卡了哦~

美好的日出 美好的山河

都因有你存在 而璀璨 耀眼

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！