首页 > 代码库 > Leetcode: Single Number
Leetcode: Single Number
Given an array of integers, every element appears twice 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: 需求里面要求O(N)时间以及无额外空间，这就排除了使用boolean array, hashmap这些个方法，只能在原数组上进行查找。O(N)基本上就相当于遍历数组，于是我就想怎么才能遍历一遍数组就知道哪个数是single的，于是就想到了需要sort一下这个数组，寻找前后元素不一样的项。
1 public class Solution { 2 public int singleNumber(int[] A) { 3 java.util.Arrays.sort(A); 4 if (A.length == 1) return A[0]; 5 int i = 1; 6 while (i < A.length) { 7 if (A[i] != A[i-1]) return A[i-1]; 8 i += 2; 9 }10 return A[i-1];11 }12 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。