면접 문제 56 - I 수조 에서 숫자 가 나 오 는 횟수
6187 단어 면접 알고리즘
한 배열 은 두 개의 숫자 가 한 번 만 나타 나 고 다른 숫자 는 두 번 나타 나 는데 어떻게 O (N) 의 복잡 도, O (1) 의 공간 복잡 도 상황 에서 이 두 개의 숫자 를 구 합 니까?
사고의 방향
이 문 제 는 전에 학교 경 기 를 할 때 해 본 적 이 있 습 니까? 아니면 아주 간단 합 니까? 다른 성질 로 우 리 는 쉽게 알 수 있 습 니 다. 모든 숫자 를 다 다 르 거나 한 번, 답 은 res = a ^ b (그 두 개의 단독 숫자의 차이 점 또는) 입 니 다. 그러면 이 res 를 어떻게 활용 합 니까?이 문 제 는 배열 을 열 수 없 기 때문에 데이터 구조 나 특정한 알고리즘 의 측면 에서 고려 할 수 없습니다. 그러면 비트 연산 으로 이 res 의 바 이 너 리 를 펼 치 는 것 을 고려 하고 res 의 특정한 바 이 너 리 를 1 로 선택 하면 a 와 b 의 차 이 는 a 와 b 의 바 이 너 리 가 이 자리 에서 다 르 면 전체 배열 로 확 장 됩 니 다.우 리 는 전체 배열 의 수 를 고려 하여 이 자리 에서 0 과 1 의 두 가지 로 나 눌 수 있다. 이 두 가지 유형 은 각자 의 차이 점 이나 화 해 를 구 하 는 것 이 바로 단독 적 인 두 개의 수 이다.
코드
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int len=nums.size();
int res=0;
for (int i=0;i<len;i++){
res=res^nums[i];
}
int bit=0;
for (int j=0;j<32;j++){
if((res>>j)&1==1){
bit=j;
break;
}
}
int a=0;
for (int i=0;i<len;i++){
if((nums[i]>>bit)&1){
a=a^nums[i];
}
}
vector<int>ans;
ans.push_back(a);
ans.push_back(res^a);
return ans;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[면접 알고리즘] 동적 기획LCS(최대 공통 하위 시퀀스) LCS(최대 공통 하위 문자열) LIS(최대 증가 하위 시퀀스) 문자열 편집 거리(문자열 유사도) 교체 문자열: 하위 시퀀스 수(Distinct Subsequences) GitHub-...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
