하나의 배열 을 정 합 니 다. 그 중에서 한 번 만 나타 나 고 다른 수 는 모두 세 번 나타 나 며 이 수 를 찾 습 니 다 (go).

1389 단어 알고리즘
1. 사고방식
두 개의 수 원 = 0, to = 0 으로 각각 bits 비트 에 1 이 나타 난 횟수 를 기록 하고 한 개의 수가 한 번 나타 나 면 one 은 이 수, to = 0 과 같다.  만약 한 수가 두 번 나타 나 면, two 는 이 수 이 고, one 은 0 이다.한 번 에 세 번 째 가 나 오 면 원 = 0, two = 0, three 는 이 수 와 같다.
우 리 는 배열 {2, 1, 2, 2} 을 예 로 들 었 다.
시작: one = 0, two = 0 three
a. 숫자 2 를 넣 으 면 one = 10 (대응 하 는 10 진법 은 2), two = 0
b. 숫자 1 을 넣 으 면 one = 11 (대응 하 는 10 진법 은 3), two = 0,  two 는 0 으로 앞의 두 숫자 가 중복 되 지 않 았 음 을 나타 낸다.
c. 숫자 2 를 넣 으 면 one = 1 (대응 하 는 10 진법 은 1), two = 10 (대응 하 는 10 진법 은 2), two 는 2 로 앞의 세 숫자 가 중복 되 는 위 치 를 나타 낸다.
d. 숫자 2 를 넣 으 면 one =  11 (대응 하 는 10 진법 은 3), two = 10 (대응 하 는 10 진법 은 2), three = one & two = 10 (10 진법 은 2) 은 숫자 자리 가 3 번 반복 되 는 것 을 나타 낸다. one = one & (^ three), two = two & (^ three), one 과 two 중 three 와 같은 자 리 를 없 애 면 3 번 나 오 는 숫자 가 떨어진다.
알고리즘: one = 0 two = 0 three
two |= one & t
one ^= t
three = one & two
one &= (^three)     python 을 사용 하면 이 곳 에 대응 하 는 것 은? one &= (~three)
two &= (^three)     python 을 사용 하면 이 곳 에 대응 하 는 것 은? two &= (~three)
 
코드 는 다음 과 같 습 니 다:
func singleNumber(nums []int) int {
	var one = 0
	var two = 0
	var three int
	for i:= 0; i < len(nums); i++ {
		temp := nums[i]
		two |= one & temp
		one ^= temp
		three = one & two
		one &= ^three
		two &= ^three
	}
	return one
}

좋은 웹페이지 즐겨찾기