검지 offer - 40 - 수조 에 한 번 밖 에 안 나 오 는 숫자.
6408 단어 알고리즘
하나의 정형 배열 에 두 개의 숫자 를 제외 하고 다른 숫자 는 모두 두 번 나 타 났 다.프로그램 을 써 서 이 두 개의 한 번 만 나 오 는 숫자 를 찾 아 보 세 요.
사고의 방향
1. HashMap 2 를 사용 할 수 있 습 니 다. 우선: 비트 연산 에서 의 이 또는 성질: 두 개의 같은 숫자 가 다 르 거나 = 0, 한 개의 수 와 0 이 또는 그 자체 입 니 다.한 개의 숫자 만 한 번 나 타 났 을 때, 우 리 는 배열 의 모든 수 를 순서대로 이동 하거나 연산 하 였 으 며, 마지막 에 남 은 것 은 한 쌍 이 나타 난 것 이 모두 상쇄 되 었 기 때문이다.
이 사고 에 따라 우 리 는 두 개의 수 (우 리 는 AB 라 고 가정) 에 한 번 나타 난 배열 을 보 았 다.우 리 는 먼저 다른 것 을 하거나 나머지 숫자 는 A, B 의 다른 결과 일 것 이다. 이 결과 의 바 이 너 리 중의 1 은 A 와 B 의 다른 위 치 를 나타 낸다.우 리 는 첫 번 째 1 이 있 는 자리 수 를 취하 고 3 위 라 고 가정 한 다음 에 원수 조 를 두 조로 나 누 었 다. 조별 기준 은 3 위 가 1 인지 아 닌 지 를 보 여 주 었 다.이와 같이 같은 수 는 한 그룹 에 있 을 것 이다. 같은 숫자 는 모든 비트 가 같 고 다른 수 는 한 그룹 에 있 지 않 을 것 이다.그 다음 에 이 두 팀 을 최초의 사고 에 따라 순서대로 다 르 거나 나머지 두 가지 결 과 는 바로 이 두 개의 한 번 만 나타 난 숫자 이다.
실현 (방법 2)
//num1,num2 1 。
// num1[0],num2[0]
/**
: : =0, 0 。
, , ,
, 。
, ( AB) 。
, A、B , 1,
A B 。 1 , 3 , ,
3 1。 , , , ,
。 ,
, 。/**
**/
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int len=array.length;
int result=0;
for(int i=0;i<len;i++){
result^=array[i];
}
int index=1;
while((index&result)==0){// !=1, result 0010 2
index=index<<1;
}
int result1=0;
int result2=0;
for(int i=0;i<len;i++){
if((array[i]&index)==0){
result1^=array[i];
}else{
result2^=array[i];
}
}
num1[0]=result1;
num2[0]=result2;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.