leetcode, LC15: single-number
1テーマの説明
整数タイプの配列があり、配列内の素は1つの要素に1回しか現れず、残りの要素は2回しか現れません.注意:追加のメモリスペースを使用せずにこの問題を解決できる線形時間複雑度のアルゴリズムが必要ですか?
Given an 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?
例1
入力
[1,0,1]
しゅつりょく
0運転時間:3 ms
2問題解決の考え方
異または異または操作を使用すると、2つの同じ数字が0または0になります.したがって、配列内のすべての数字は、求められた数字である.
3コード実装
4運転結果
実行時間:3 msメモリ消費量:504 k
整数タイプの配列があり、配列内の素は1つの要素に1回しか現れず、残りの要素は2回しか現れません.注意:追加のメモリスペースを使用せずにこの問題を解決できる線形時間複雑度のアルゴリズムが必要ですか?
Given an 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?
例1
入力
[1,0,1]
しゅつりょく
0運転時間:3 ms
2問題解決の考え方
異または異または操作を使用すると、2つの同じ数字が0または0になります.したがって、配列内のすべての数字は、求められた数字である.
3コード実装
class Solution {
public:
/**
*
* @param A int
* @param n int A
* @return int
*/
int singleNumber(int* A, int n) {
// write code here
int singleNum = 0;
for(int i = 0; i < n; i++)
singleNum ^= A[i];
return singleNum;
}
};
4運転結果
実行時間:3 msメモリ消費量:504 k