题目
给出2*n + 1 个的数字,除其中一个数字之外其他每个数字均出现两次,找到这个数字。
http://www.lintcode.com/zh-cn/problem/single-number/
分析
由于除目标数之外的其他数字,都会出现两次,很容易联想到抵消。假设有一个容器,向其中添加数时,若该数不存在,就存储下来,若存在,就删除掉这个数。当所有的数字都添加到容器中后,容器中唯一剩下的数就是要早的落单数。
那么,应该用什么充当容器呢?容器会频繁进行增加和删除的操作,数组并不合适,带头节点的单链表是一个不错的选择。插入数字时,若链表中不包含这个数字,就创建一个新节点添加到链表末尾;若存在,就删除对应的节点。数组遍历结束后,头节点后面的节点,存储的就是落单的数。
代码
主要就是实现一个(带头节点的)单链表的查找和删除。删除时注意一下删除末尾元素的特殊情况即可。
class ListNode{
ListNode next;
int val;
ListNode(){
this.next = null;
}
ListNode(int val){
this.val = val;
this.next = null;
}
}
class List{
ListNode head = null;
ListNode last = null;
List(){
head = last = new ListNode();
}
void add(int val){
last.next = new ListNode(val);
last = last.next;
}
// 查找目标值的前驱节点,由于有头节点的存在,直接从头节点后面的第一个元素开始
ListNode findPrevious(int val){
for(ListNode pre = head; pre.next != null; pre = pre.next){
if(pre.next.val == val) return pre;
}
return null;
}
//删除节点,若被删除的节点为last时,需要更新last
void remove(ListNode node){
ListNode target = node.next;
node.next = target.next;
if(target == this.last){
this.last = node;
}
}
void addOrRemove(int val){
ListNode pre = this.findPrevious(val);
if(pre == null){
this.add(val);
}else{
this.remove(pre);
}
}
}
public class Solution {
/*
* @param A: An integer array
* @return: An integer
*/
public int singleNumber(int[] A) {
// write your code here
List list = new List();
for(int i=0; i < A.length; i++){
list.addOrRemove(A[i]);
}
return list.last.val;
}
}