Lettcode_136_Single Number
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)주 제 는 하나의 성형 배열 을 정 하 는 것 이다.그 중에서 배열 에서 한 요 소 를 제외 하고 다른 임 의 요소 가 두 번 나타 나 고 한 번 만 나타 나 는 요 소 를 원한 다.
(2)문제 가 시간 복잡 도 를 선형 으로 제한 하기 때문에 for 순환 이 여러 번 나타 나 지 못 하고 추가 공간 을 신청 하지 않 는 것 이 좋 습 니 다.이렇게 되면 우 리 는 어떻게 배열 을 한 번 옮 겨 다 니 는 상황 에서 한 번 나타 난 요 소 를 찾 을 수 있 는 지 생각해 야 한다.같은 요 소 를 없 앨 수 있 는 방법 을 생각 할 수 있 는 지 를 고려 하여 우 리 는 흔히 볼 수 없 는 특수 연산 자'^'-비트 별 또는 연산 을 사용 해 야 한다.우 리 는 이 또는 연산 이 같은 비트 가 제거 된다 는 것 을 알 고 있 습 니 다.예 4^4=(이 진)10^(이 진)10=(이 진)00 은 같은 숫자 를 제거 합 니 다.배열 에서 같은 숫자 가 비 연속 적 이 더 라 도 덧셈 의 교환 율 에 따라 같은 결 과 를 얻 을 수 있다.
(3)본문 이 당신 에 게 도움 이 되 기 를 바 랍 니 다.
알고리즘 코드 는 다음 과 같 습 니 다.
/**
* @author liqq
*/
public static int singleNumber(int[] A) {
if (A.length == 0)
return A[0];
int x = A[0];
for (int i = 1; i < A.length; i++) {
x = x ^ A[i];
}
return x;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
