算法练习(18) - 第一个唯一数字

惊羽-布壳儿

发布于 2022-06-15 16:09:44

1480

发布于 2022-06-15 16:09:44

文章被收录于专栏：惊羽-布壳儿

题目

给一个连续的数据流,写一个函数返回终止数字到达时,终止数字前面出现的第一个唯一数字即只出现一次的函数（包括终止数字）,如果在终止数字前无唯一数字或者找不到这个终止数字, 返回 -1。

Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirst [[[2,3,5]],[],[5],[],[2],[],[3],[]] Output: [null,2,null,2,null,3,null,-1]

Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirstUnique(); // return 2 firstUnique.add(2); // the queue is now [2,3,5,5,2] firstUnique.showFirstUnique(); // return 3 firstUnique.add(3); // the queue is now [2,3,5,5,2,3] firstUnique.showFirstUnique(); // return -1

题解

import java.util.HashMap;
import java.util.LinkedList;

public class FirstUnique {

    LinkedList<Integer> linkedList = new LinkedList<>();
    LinkedList<Integer> temp = new LinkedList<>();
    HashMap<Integer,Integer> hashMap = new HashMap<>();

    private int showFirstUnique() {
        while (linkedList.peek() != null){
            Integer pop = linkedList.pop();
            if(hashMap.get(pop) < 2){
                return pop;
            }
            temp.offer(pop);
        }
        LinkedList<Integer> t = temp;
        temp = linkedList;
        linkedList = t;
        return -1;
    }

    public static void main(String[] args) {

        FirstUnique firstUnique = new FirstUnique();
        firstUnique.add(2);
        firstUnique.add(3);
        firstUnique.add(5);
        System.out.println(firstUnique.showFirstUnique());
        firstUnique.add(2);
        System.out.println(firstUnique.showFirstUnique());
    }

    private void add(int i) {
        if(hashMap.get(i) != null){
            hashMap.put(i,hashMap.get(i)+1);
        }else{
            hashMap.put(i,1);
        }
        linkedList.offer(i);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

bash