当前位置:网站首页>[algorithm] sword finger offer2 golang interview question 4: numbers that appear only once
[algorithm] sword finger offer2 golang interview question 4: numbers that appear only once
2022-07-06 12:51:00 【Deng Jiawen jarvan】
[ Algorithm ] The finger of the sword offer2 golang Interview questions 4: A number that appears only once
subject 1:
Give you an array of integers nums , Except that one element only appears once Outside , Every other element just happens to appear Three times . Please find and return the element that only appears once .
Example 1:
Input :nums = [2,2,3,2]
Output :3
Example 2:
Input :nums = [0,1,0,1,0,1,100]
Output :100
Tips :
1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums in , Except that one element only appears once Outside , Every other element just happens to appear Three times
Advanced : Your algorithm should have linear time complexity . Can you do this without using extra space ?
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/WGki4K
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas 1:
// Ideas : appear 3 Time , Use bs []int To record 32 Single digit 1 The number of
// If bs[i] The number of is 0 perhaps 3 Multiple , let bs[i] = 0, conversely bs[i] =1
// Final material bs => int
Code
func singleNumber(nums []int) int {
// Ideas : appear 3 Time , Use bs []int To record 32 Single digit 1 The number of
// If bs[i] The number of is 0 perhaps 3 Multiple , let bs[i] = 0, conversely bs[i] =1
// Final material bs => int
// Processing parameters
if len(nums) == 0 {
return 0
}
// structure bs
bs := make([]int,32)
// Traverse element to bs assignment
for i := 0; i < len(nums); i++ {
for j := 0; j < 32; j++ {
if (nums[i] & (1<<j)) != 0 {
bs[j] ++
}
}
}
//bs[i] The number of is 0 perhaps 3 Multiple , let bs[i] = 0, conversely bs[i] =1
for j := 0; j < 32; j++ {
if bs[j]%3 != 1 {
bs[j] = 0
}else {
bs[j] = 1
}
}
// format bs by res int
//tips: bug golang 64 Bit machine int Namely 64 position
var res int32
for j := 0; j < 32; j++ {
if bs[j] == 1 {
res = res | (1 << j)
}
}
return int(res)
}
test
边栏推荐
- MySQL shutdown is slow
- Game 280 weekly
- It has been solved by personal practice: MySQL row size too large (> 8126) Changing some columns to TEXT or BLOB or using ROW_ FORMAT
- Get the position of the nth occurrence of the string
- Itext 7 生成PDF总结
- 1041 Be Unique (20 point(s))(哈希:找第一个出现一次的数)
- 基本Dos命令
- Esp8266 connect onenet (old mqtt mode)
- Easy to use shortcut keys in idea
- Liste des boucles de l'interface graphique de défaillance
猜你喜欢
[算法] 剑指offer2 golang 面试题13:二维子矩阵的数字之和
第一人称视角的角色移动
FairyGUI循环列表
[Clickhouse kernel principle graphic explanation] about the collaborative work of partitioning, indexing, marking and compressed data
Fabrication of fairygui simple Backpack
[算法] 剑指offer2 golang 面试题5:单词长度的最大乘积
Naive Bayesian theory derivation
MySQL shutdown is slow
抗差估计在rtklib的pntpos函数(标准单点定位spp)中的c代码实现
(core focus of software engineering review) Chapter V detailed design exercises
随机推荐
[leetcode622]设计循环队列
Unity3d, Alibaba cloud server, platform configuration
(the first set of course design) sub task 1-5 317 (100 points) (dijkstra: heavy edge self loop)
SVN更新后不出现红色感叹号
Force buckle 1189 Maximum number of "balloons"
Excel导入,导出功能实现
[算法] 劍指offer2 golang 面試題2:二進制加法
[leetcode15] sum of three numbers
Solution to the problem of automatic login in Yanshan University Campus Network
In 2020, the average salary of IT industry exceeded 170000, ranking first
[offer78] merge multiple ordered linked lists
Fairygui character status Popup
Itext 7 生成PDF总结
[899] ordered queue
FairyGUI条子家族(滚动条,滑动条,进度条)
Halcon knowledge: gray_ Tophat transform and bottom cap transform
KF UD分解之UD分解基础篇【1】
Detailed explanation of truncate usage
[Leetcode15]三数之和
[offer18] delete the node of the linked list