49 lines
1.0 KiB
Go
49 lines
1.0 KiB
Go
|
/*
|
|||
|
|
* @Author : huangzj
|
|||
|
|
* @Time : 2021/3/18 13:08
|
|||
|
|
* @Description：
|
|||
|
|
*/
|
|||
|
|
|
|||
|
|
package NumberCount
|
|||
|
|
|
|||
|
|
type OnlyOneNumberOtherKObj struct{}
|
|||
|
|
|
|||
|
|
func (*OnlyOneNumberOtherKObj) Doc() string {
|
|||
|
|
return `
|
|||
|
|
给定一个整型数组 arr和一个大于1的整数k。已知 arr中只有1个数出现了1次，其他的数都出现了k次，请返回只出现了1次的数。
|
|||
|
|
|
|||
|
|
【要求】
时间复杂度为 O（N），额外空间复杂度为 O（1）。
|
|||
|
|
`
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
func OnlyOneNumberOtherK(numList []int, k int) int {
|
|||
|
|
bitList := make([]int, 32)
|
|||
|
|
for _, num := range numList {
|
|||
|
|
//把每个数字转换成二进制
|
|||
|
|
store := make([]int, 32)
|
|||
|
|
for i := 0; num != 0; i++ {
|
|||
|
|
store[i] = num % k
|
|||
|
|
num = num / k
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
for j := 0; j < 32; j++ {
|
|||
|
|
//不进位加法
|
|||
|
|
bitList[j] = (store[j] + bitList[j]) % k
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
//k进制转换回十进制
|
|||
|
|
power := 1 //k的次方值
|
|||
|
|
result := 0 //只出现一次的数字
|
|||
|
|
for i, bit := range bitList {
|
|||
|
|
power = 1
|
|||
|
|
for j := 0; j < i; j++ {
|
|||
|
|
power = power * k
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
result = result + power*bit
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
return result
|
|||
|
|
}
|