如何优化代码(java)

Question

我有一个任务.当用户在网站上注册时,他的id可以是他最喜欢的号码.但是如果已经存在具有这种id的用户,则该用户的id成为跟随他最喜欢的号码的最小空闲号码.但是当游客离开现场时,他的标识符不再被占用,下一个用户可以占用他的身份.例如:

Input:
first line value `n` is amount of users
the next `n` lines contain two values: first value can be 1  if user register on site or 2 if user leave site
 second value is favorite number (1<=x<=1000000000)
Input:
7
1 10
1 10
1 10
1 11
1 20
2 11
1 11

Output:
10
11
12
13
20
11

这是我的代码:

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
 public static final Scanner in= new Scanner(System.in);
 public static final int SIZE = 2;
 public static final int MAXNUMBER = 1000000000;
    public static void main(String[] args) {
        int t = Integer.parseInt(in.nextLine());
        Map<Integer, Integer> favoriteNumbers = new HashMap<>();
        int []a = new int[SIZE];
        while(t-- > 0) {
            for(int i=0; i<SIZE; i++) {
                a[i] = in.nextInt();
            }
            if(a[0] == 1 && !favoriteNumbers.containsValue(a[1])) {
                System.out.println(a[1]);
                favoriteNumbers.put(a[1], a[1]);
            }
            else if (a[0] == 1 && favoriteNumbers.containsValue(a[1])) {
                for(int i= (a[1] + 1); i<MAXNUMBER; ) {
                    if(!favoriteNumbers.containsValue(i)) {
                        System.out.println(i);
                        favoriteNumbers.put(i, i);
                        break;
                    }
                    i++;
                }
            } else if(a[0] == 2 && favoriteNumbers.containsValue(a[1])){
                favoriteNumbers.remove(a[1], a[1]);
            }
        }
    }
}

它运行正常,但我的运行时间超出了.最长执行时间应为1秒.请帮助我如何优化代码并加快运行时间.

Answer 1

favoriteNumbers.containsValue(a[1])需要线性时间(因为在HashMap需要迭代所有值时找到一个值).favoriteNumbers.containsKey(a[1])需要不断的时间.

当然,由于地图的键和值是相同的,因此您应该使用HashSet而不是HashMap,并且一旦更改favoriteNumbers为a HashSet,favoriteNumbers.contains(a[1])将花费不变的时间.

这是使用的优化版本HashSet.编辑:

import java.util.*;

public class Main {
    public static final Scanner in= new Scanner(System.in);
    public static final int SIZE = 2;
    public static final int MAXNUMBER = 1000000000;

    public static void main(String[] args) {
        int t = Integer.parseInt(in.nextLine());
        StringBuilder sb = new StringBuilder("");
        Set<Integer> favoriteNumbers = new HashSet<>();
        int []a = new int[SIZE];
        while(t-- > 0) {
            for(int i=0; i<SIZE; i++) {
                a[i] = in.nextInt();
            }
            if(a[0] == 1) {
                for(int i = a[1]; i < MAXNUMBER; i++) {
                    if (favoriteNumbers.add(i)) {
                        sb.append(i + "\n");
                        break;
                    }
                }
            } else if(a[0] == 2) {
                favoriteNumbers.remove(a[1]);
            }
        }
        System.out.println(sb.toString());
    }
}