离散化模版

离散化模版

import java.util.*;

public class Discretizing {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		List<Integer> values = new ArrayList<Integer>();
		// 存储所有待离散化的值
		ArrayList<Integer> alls = new ArrayList<>();

		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			values.add(sc.nextInt());
		}
		// 使用Hashset去除重复元素，并转化为List
		alls = new ArrayList<>(new HashSet<>(values));
		Collections.sort(alls); //将所有值排序
		int k = sc.nextInt();
		System.out.print(find(k,alls));

	}

	//二分查找求出x对应的离散化的值
	public static int find(int x, ArrayList<Integer> alls) {
		int l = 0, r = alls.size();
		while (l < r) {
			int mid = l + r >> 1;
			if (alls.get(mid) >= x) {
				r = mid;
			} else
				l = mid + 1;
		}

		return r + 1; //映射到1，2,3···n
	}

}