落单的数

题目

给出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;
    }
}
Show Comments

Get the latest posts delivered right to your inbox.