本文主要是介绍【leetcode78】Single Number II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述:
给定一个数组,里面除了一个数字,其他的都出现三次。求出这个数字
原文描述:
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Subscribe to see which companies asked this question
思路:
- 设置一个32位的数组,然然后对数组,Array【i】代表i位的1个数,统计整个数组nums【】的数字,对于每个Array【i】做mod3的运算
- 遍历nums【】数组时候,是左移&1取出,加到Array【i】上面,然后mod3
- 最后右移加到result上面
代码:
// Single Number II
// 方法1,时间复杂度O(n),空间复杂度O(1)
public class Solution {public int singleNumber(int[] nums) {final int W = Integer.SIZE; // 一个整数的bit数,即整数字长int[] count = new int[W]; // count[i]表示在在i位出现的1的次数for (int i = 0; i < nums.length; i++) {for (int j = 0; j < W; j++) {count[j] += (nums[i] >>> j) & 1;count[j] %= 3;}}int result = 0;for (int i = 0; i < W; i++) {result += (count[i] << i);}return result;}
};
更多的leetcode的经典算法,查看我的leetcode专栏,链接如下:
leetcode专栏
这篇关于【leetcode78】Single Number II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!