首页 > 代码库 > Leetcode: Single Number II
Leetcode: 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?
Analysis: 注意那个single one的个数可能比3少，也可能比3多。所以想法就是先sorting，然后从小到大遍历每个元素，前后元素相同时counter++，不相同时看counter是否为3，不是的话就返回前一个元素，是的话counter重新置1. 特殊情况在于single one在最后，所以如果循环执行完了函数都还没有return，说明single one是最后的元素。要注意，对于这种需要返回值的function, 不能所有的return都在if语句里
1 public class Solution { 2 public int singleNumber(int[] A) { 3 java.util.Arrays.sort(A); 4 int count = 1; 5 int i; 6 for (i = 1; i < A.length; i++) { 7 if (A[i] == A[i-1]) { 8 count++; 9 }10 else {11 if (count != 3) return A[i-1];12 count = 1;13 }14 }15 return A[i-1];16 }17 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。