java - 如何优化代码(java)

Question

我有一个任务。当用户在网站上注册时，他的 ID 可以是他最喜欢的号码。但如果已经有一个用户有这样的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 > 对于 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());
    }
}