어떻게 C 언어 비트 연산 을 이용 하여 한 번 만 나타 나 는 숫자 를 해결 합 니까?

문제 풀이 에 필요 한 C 언어 기초 지식
hello！지금부터 본 문제 풀이 의 정식 내용 으로 들 어 갑 니 다.먼저 C 언어 비트 연산 의 기본 연산 자 3 개 를 도해 로 소개 합 니 다&|^

이런 지식 들 은 아래 의 문제 풀이 에 매우 중요 하 므 로 반드시 숙련 되 어야 한다.그렇지 않 으 면'내 가 어디 에 있 는 지,내 가 누구 인지,내 가 무엇 을 하고 있 는 지'라 는 느낌 이 들 것 이다.
한 번 밖 에 안 나 오 는 숫자 I
제목 설명
한 번 밖 에 안 나 오 는 숫자.
빈 정수 가 아 닌 배열 을 지정 합 니 다.특정한 요소 가 한 번 만 나타 나 는 것 을 제외 하고 나머지 모든 요 소 는 두 번 씩 나타 납 니 다.한 번 밖 에 나타 나 지 않 은 원 소 를 찾 아 라.
설명:
너의 알고리즘 은 선형 시간 복잡 도 를 가 져 야 한다.당신 은 추가 공간 을 사용 하지 않 고 실현 할 수 있 습 니까?
예시 1:
입력:[2,2,1]출력:1
예시 2:
입력:[4,1,2,1,2]출력:4
힘 단추 본제 링크
문제 풀이 의 사고 방향.
우선,제목 의 뜻 에 따라'공간 을 추가 로 사용 할 수 없 는 한정 이 있 습 니까?'라 는 제한 이 있 습 니 다.여 기 를 본 후에 본능적으로 비트 연산 위 에 기대 야 합 니 다.비트 연산 은 추가 공간 을 개척 하지 않 고 많은 문 제 를 해결 할 수 있 기 때 문 입 니 다.그리고 방금 돌 이 켜 본 비트 연산 지식 을 돌아 보면 우리 가^이 조작 부 호 를 사용 해 야 한 다 는 것 을 알 수 있 습 니 다.중복 항목 을 간단하게 제거 할 수 있 기 때 문 입 니 다.한 번 밖 에 나 오지 않 은 숫자.
이렇게 많아

int singleNumber(int* nums, int numsSize){
int ret=0;//0               
for(int i=0;i<numsSize;i++)
{
 ret^=nums[i];//     ，     ，          
}
return ret;//      
}

이것 은 단지 식욕 을 돋 우 는 요리 일 뿐,다음은 정식으로 메 인 요리 에 들어간다.
한 번 밖 에 안 나 오 는 숫자 II
제목 설명
한 번 만 나타 나 는 숫자 II 는 빈 정수 가 아 닌 배열 을 정 하고 특정한 요소 가 한 번 만 나타 나 는 것 을 제외 하고 나머지 모든 요 소 는 세 번 나 타 났 다.한 번 밖 에 나타 나 지 않 은 원 소 를 찾 아 라.
설명:
너의 알고리즘 은 선형 시간 복잡 도 를 가 져 야 한다.당신 은 추가 공간 을 사용 하지 않 고 실현 할 수 있 습 니까?
예시 1:
입력:[2,2,3,2]출력:3
`예시 2:
입력:[0,1,0,1,0,1,99]출력:99
힘 단추 본제 링크
문제 풀이 의 사고 방향.
그림 에서 보 듯 이 숫자의 바 이 너 리 형식 을 고려 하여 세 번 의 숫자 가 나타 나 고 바 이 너 리 여러분 의 1 은 모두 3 의 배수 이기 때문에 여러분 의 1 수 를 구하 고 3 에 나머지 를 구하 면 한 번 만 나타 나 는 숫자 를 구 할 수 있 습 니 다.

그러면 바 이 너 리 여러분 의 1 의 숫자 를 어떻게 구 해 야 합 니까?그러면&이 조작 자 를 사용 해 야 합 니 다.코드 가 실현 되 는 지 보 겠 습 니 다.

int singleNumber(int* nums, int numsSize){
 
 int ret=0;
for(int i=0;i<32;++i)//           
{
long cnt=0;//  long，         ，  int    31 ，     
 for(int j=0;j<numsSize;++j) {// nums          ，        i ， 1   ，
 cnt+=(nums[j]>>i)&1;//         i    1；
 }
 ret+=(cnt%3)<<i;// cnt   3，            i  1   0，     i   ，         
}
return ret;
}

자,이 문 제 는 원만 하 게 해결 되 었 다.
한 번 만 나 오 는 숫자 III
이 문 제 는 아주 기교 가 있 습 니 다.제목 설명.
260.한 번 만 나타 나 는 숫자 III 는 하나의 정수 그룹 nums 를 지정 하 는데 그 중에서 마침 두 개의 요소 가 한 번 만 나타 나 고 나머지 모든 요 소 는 두 번 씩 나타난다.한 번 밖 에 나타 나 지 않 는 그 두 원 소 를 찾 아 라.너 는 임의의 순서에 따라 답안 을 되 돌려 줄 수 있다.
진급:당신 의 알고리즘 은 선형 시간 복잡 도 를 가 져 야 합 니 다.당신 은 상수 공간의 복잡 도 만 사용 하여 실현 할 수 있 습 니까?
예시 1:
입력:nums=[1,2,1,3,2,5]출력:[3,5]해석:[5,3]도 유효한 답안 이다.
예시 2:
입력:nums=[-1,0]출력:[-1,0]
예시 3:
입력:nums=[0,1]출력:[1,0]
힘 단추 본제 링크
문제 풀이 의 사고 방향.
첫 번 째 문제 의 사고 에 따라 모두 위치 에 따라 다 르 거나 중복 항 을 없 애 야 한 다 는 것 을 알 수 있다.그러나 두 개의 한 번 만 나타 난 숫자 도 다 르 거나 함께 있 었 다.우리 의 어 려 운 점 은 이 두 수 를 어떻게 분리 하 느 냐 하 는 것 이다.이제 두 개의 숫자 를 어떻게 분리 하 는 지 보 여 드 리 도록 하 겠 습 니 다.

다음은 코드 의 실현 이다.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize){
int m = 0;
int ret = 0;
for (int i = 0; i < numsSize; i++)
{
	ret ^= nums[i];//      
}
while (m < 32)
{
	if ((ret>>m)&1)//   1  m 
		break;
	else
  ++m;
}
int x1 = 0, x2 = 0;//  
int j=0;
while(j<numsSize)
{
	if ((nums[j]>>m)&1)
		x1 ^= nums[j];//           
	else
		x2 ^= nums[j];
  j++;
}
int* reRer = (int*)malloc(sizeof(int) * 2);
reRer[0] = x1;
reRer[1] = x2;
*returnSize=2;//        
return reRer;//      
}

소 편 총화
이것 은 내 가 처음으로 문 제 를 푸 는 것 이다.상대 적 으로 간단 하고 흔히 볼 수 있 는 세 개의 문 제 를 골 랐 는데 어렵 지 않 지만 문 제 를 푸 는 사상 도 나 타 낼 수 있다.나 는 모두 가 이 세 문 제 를 간단하게 배 우 는 것 이 아니 라 이런 사상 을 배 워 서 더 많은 문 제 를 해결 하 기 를 바란다.그리고 여러분 들 은 좋 은 문제 풀이 방안 을 가지 고 댓 글 에 댓 글 을 남 길 수 있 습 니 다.서로 공부 하고 함께 발전 할 수 있 습 니 다.
C 언어 비트 연산 을 이용 하여 숫자 가 한 번 밖 에 나 오지 않 는 문 제 를 해결 하 는 방법 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C 언어 비트 연산 해결 에 숫자 내용 이 나 오 면 저희 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 저 희 를 많이 응원 해 주시 기 바 랍 니 다!