LeetCode #136 SingleNumber. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
3종류로 풀었는데 퍼포먼스가 중간 정도밖에 안나오길래 다른사람들 것을 봤더니 xor 를 이용해서 풀었다.
간단한데 xor 관련 연산자들이 2진수 연산인걸 몰랐음. 좀 더 봐야겠다.
xor >>>>>> sort >>> map >>>>>>>>>>>>>> iteration twice 의 순서로 퍼포먼스가 나왔다.
I solved it with 3 different solution, but max performance was just half of others. So I saw others and re-try with xor operation.
It was simple, but i didn't know that xor operation is about binary. I should study more about it.
performance was..
xor >>>>>> sort >>> map >>>>>>>>>>>>>> iteration twice
LeetCode #136
Q.
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?
비어있지 않은 정수 배열에서, 모든 값들은 두번씩 나오고, 한개만 한번 나온다. 그 한개 값을 찾아라.
노트 :
선형의 런타임 시간복잡도를 가져야 한다. 추가 메모리 사용없이 구현 가능한가?
e.g.
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
Process
// Process
//1. Input integer array
//2. Iterate from begin to the end
// 2.1. Check if it has same number
//3. Return single number
// 처리과정
//1. 정수배열 입력받는다.
//2. 시작부터 끝까지 반복한다.
// 2.1. 같은 수가 있는지 확인한다.
//3. 한개인 수를 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
class Solution {
public:
int singleNumber(vector<int>& nums) {
int num = 0;
for (int i = 0; i < nums.size(); ++i) {
num = num ^ nums[i];
}
return num;
}
//int singleNumber(vector<int>& nums) {
// if (nums.size() == 1)
// return nums[0];
// sort(nums.begin(), nums.end());
// for (int i = 0; i < nums.size() - 2; i += 2)
// {
// if (nums[i] != nums[i + 1])
// {
// return nums[i];
// }
// }
// return nums[nums.size()-1];
//}
//int singleNumber(vector<int>& nums) {
// bool hasSame;
// for (int i = 0; i < nums.size(); ++i)
// {
// hasSame = false;
// int j = i+1;
// while (!hasSame && j < nums.size())
// {
// if (nums[i] == nums[j])
// {
// hasSame = true;
// nums.erase(nums.begin() + j);
// }
// ++j;
// }
// if (!hasSame)
// return nums[i];
// }
// return 0;
//}
//int singleNumber(vector<int>& nums) {
// map<int, int> tempMap;
// for (int i = 0; i < nums.size(); ++i)
// {
// auto search = tempMap.find(nums[i]);
// if (search != tempMap.end()) {
// tempMap.erase(nums[i]);
// }
// else
// {
// tempMap.insert(pair<int, int>(nums[i], nums[i]));
// }
// }
// return tempMap.begin()->first;
//}
};
int main(int argc, char *argv[]) {
//cout << "Hell" << endl;
vector<int> input; // 2 4 4 2 3 5 3
input.push_back(2);
input.push_back(2);
input.push_back(3);
input.push_back(5);
input.push_back(3);
Solution sln;
cout << sln.singleNumber(input) << endl;
}
Something else you might like...?
2019/02/03 - [Algorithm/Leet Code] - LeetCode #393 UTF-8 Validation. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/03 - [Algorithm/Leet Code] - LeetCode #398 RandomPickIndex. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/02/01 - [Algorithm/Leet Code] - LeetCode #905 SortArrayByParity. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/31 - [Algorithm/Leet Code] - LeetCode #593 ValidSquare. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/16 - [Algorithm/Leet Code] - LeetCode #217 ContainsDuplicate. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/21 - [Algorithm/Leet Code] - LeetCode #219 ContainsDuplicate2. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/22 - [Algorithm/Leet Code] - LeetCode #220 ContainsDuplicate3. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2019/01/23 - [Algorithm/Leet Code] - LeetCode #225 ImplementStackUsingQueue. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
2018/10/19 - [Programming/Design Pattern ] - Design pattern - Prototype (디자인패턴 - 프로토타입) / Java C++ C#
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #60 sudoku. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/12 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #59 spiralNumbers. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/08 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #58 messageFromBinaryCode. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/07 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #57 fileNaming. Algorithm,알고리즘,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive
2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #56 digitsProduct. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar
2019/01/04 - [Algorithm/Code Fights (Code Signal)] - Aracade Intro #55 differentSquares. Algorithm, 알고리즘, Codefights, CodeSignal, 코드파이트, 코드시그널, 예제,문제해결능력,example, c++ java c# scalar
2018/12/28 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 - (#9, Tell, Don't Ask)
2018/12/26 - [Programming/Software Architecture] - Perfecting OO's Small Classes and Short Methods. 완벽한 객체지향의 작은 클래스와 짧은 메소드, Book:ThoughtWorks Anthology, Java,cpp,자바,oop,좋은코드,객체지향프로그래밍 (1)
2019/01/14 - [Programming/Java] - 자바 메모리 누수 체크/확인/고치는 방법, Memory leak check/fix in Java application, cleanCode/좋은코드/oop/객체지향
2019/01/25 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(3)
2018/12/16 - [Life/Health care] - L-Arginine 아르기닌 usage/side effects/dosage 효능/부작용/성인,소아 용법(2)
2018/12/27 - [Life/Health care] - Milk-Thistle 밀크시슬 usage/side effects/dosage/fatigue/supplement,효능/부작용/성인,소아 용법/건강/피로회복/영양제
2018/12/26 - [Life/Health care] - Selenium 셀레늄 usage/side effects/dosage 효능/부작용/성인,소아 용법