LeetCode 137. Single Number II

再来一道，刷简单题。

 

137. 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?

 

题目思路和136一致，只需要将步长设为3即可，分析过程见我blog

http://leonard1853.iteye.com/blog/2275626

  

public class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        
        int index = 0;
        while(index < nums.length - 2) {
            if (nums[index] - nums[index + 1] == 0 && nums[index] - nums[index + 2] == 0) {
                index += 3;
            } else {
                return nums[index];
            }
        }
        return nums[index];
    }
}

 

 

评论

2 楼 leonard1853 2016-02-22  

mrpanyu 写道

也是基于“异或”那种思路，用三进制不进位加法

三进制不太好写，以下代码是二进制三进制混用

Integer[] arr = new Integer[] { 3, 3, 3, 4, 4, 4, 5, 5, 5, 7, 7, 7, 9, 11, 11, 11, 13, 13, 13 };
List<Integer> list = Arrays.asList(arr);
Collections.shuffle(list); // 打乱顺序
System.out.println(Arrays.toString(arr));

// 下面是实际计算部分
byte[] data = new byte[32];
for (int i = 0; i < arr.length; i++) {
int num = arr[i];
String strBinaryNum = Integer.toBinaryString(num);
int leadingZeros = Integer.numberOfLeadingZeros(num);
for (int j = leadingZeros; j < 32; j++) {
byte x = data[j];
char y = strBinaryNum.charAt(j - leadingZeros);
if (y == '1') {
x++;
if (x == 3) {
x = 0;
}
data[j] = x;
}
}
}

StringBuilder sb = new StringBuilder();
for (int i = 0; i < data.length; i++) {
sb.append(data[i]);
}

int singleNum = Integer.parseInt(sb.toString(), 2);
System.out.println(singleNum);

非常赞哦，领教了！

1 楼 mrpanyu 2016-02-05  

也是基于“异或”那种思路，用三进制不进位加法

三进制不太好写，以下代码是二进制三进制混用

Integer[] arr = new Integer[] { 3, 3, 3, 4, 4, 4, 5, 5, 5, 7, 7, 7, 9, 11, 11, 11, 13, 13, 13 };
List<Integer> list = Arrays.asList(arr);
Collections.shuffle(list); // 打乱顺序
System.out.println(Arrays.toString(arr));

// 下面是实际计算部分
byte[] data = new byte[32];
for (int i = 0; i < arr.length; i++) {
int num = arr[i];
String strBinaryNum = Integer.toBinaryString(num);
int leadingZeros = Integer.numberOfLeadingZeros(num);
for (int j = leadingZeros; j < 32; j++) {
byte x = data[j];
char y = strBinaryNum.charAt(j - leadingZeros);
if (y == '1') {
x++;
if (x == 3) {
x = 0;
}
data[j] = x;
}
}
}

StringBuilder sb = new StringBuilder();
for (int i = 0; i < data.length; i++) {
sb.append(data[i]);
}

int singleNum = Integer.parseInt(sb.toString(), 2);
System.out.println(singleNum);