本文共 1503 字,大约阅读时间需要 5 分钟。
LeetCode刷题:137. Single Number II
原题链接:
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2]
Output: 3 Example 2:Input: [0,1,0,1,0,1,99]
Output: 99算法设计
package com.bean.algorithm.basic;import java.util.HashSet;public class SingleNumberII { public static int singleNumber(int[] nums) { HashSet set1 = new HashSet(); HashSet set2 = new HashSet(); for (int i = 0; i < nums.length; i++) { if (set1.contains(nums[i])) { set2.add(nums[i]); } else { set1.add(nums[i]); } } int i = 0; for (Object o : set1) { if (set2.contains(o)) { } else { i = (Integer) o; } } return i; } public static void main(String[] args) { // TODO Auto-generated method stub int[] arrays=new int[] {0,1,0,1,0,1,99}; int ANSWER = singleNumber(arrays); System.out.println("ANSWER = "+ANSWER); }}
程序运行结果:
ANSWER = 99
第二种算法设计
public static int singleNumber(int[] nums) { if (nums == null || nums.length == 0) return 0; Arrays.sort(nums); // sort array int i = 1; while (i <= nums.length - 3) { if (nums[i - 1] == nums[i] && nums[i] == nums[i + 1]) { i += 3; } else { if (nums[i - 1] != nums[i] && nums[i] == nums[i + 1]) return nums[i - 1]; if (nums[i - 1] == nums[i] && nums[i] != nums[i + 1]) return nums[i + 1]; } } return nums[nums.length - 1];}
转载地址:http://fitdi.baihongyu.com/