【LeetCode】136. Single Number
- 2019 年 11 月 8 日
- 筆記
版權聲明:本文為博主原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
本文鏈接:https://blog.csdn.net/shiliang97/article/details/102092957
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1] Output: 1 Example 2:
Input: [4,1,2,1,2] Output: 4
來源:力扣(LeetCode) 鏈接:https://leetcode-cn.com/problems/single-number 著作權歸領扣網絡所有。商業轉載請聯繫官方授權,非商業轉載請註明出處。
這道題用異或做太火了。。。。
class Solution { public: int singleNumber(vector<int>& nums) { int num=0; for(auto it :nums){ num ^= it; } return num; } };
想了一個,排序然後倆倆一對兒
class Solution { public: int singleNumber(vector<int>& nums) { int n =nums.size(); if(n==1){ return nums[0]; } sort(nums.begin(),nums.end()); int i=0; while(i+1<n){ if(nums[i]!=nums[i+1]){ return nums[i]; } i=i+2; } return nums[i]; } };