不同整数的最少数目和单词直接最短距离

本文主要是介绍不同整数的最少数目和单词直接最短距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

写是为了更好的思考，坚持写作，力争更好的思考。
今天分享两个关于“最小、最短”的算法题，废话少说，show me your code！

一、不同整数的最少数目

给你一个整数数组arr和一个整数k。现需要从数组中恰好移除k个元素，请找出移除后数组中不同整数的最少数目？
输入：
arr=[5,4,5],k=1
输出：1
解释：
移除1个4，数组中只剩下5一种整数
输入：
arr=[4,3,1,1,3,3,2],k=3
输出：2 解释：先移除4,2然后再移除两个1中任意1个1或者移除两个3中的任意1个3，最后剩余1和3两种整数类型

public static int getMinDifference(int[] arr, int k) {// key存放数组数字，value存放次数Map<Integer, Integer> map = new HashMap<>();for (int i : arr) {map.put(i, map.getOrDefault(i, 0) + 1);}// 对次数按照自然顺序排序即由小到大List<Integer> countNumList = map.values().stream().sorted().collect(Collectors.toList());// 不同种类组成的list的长度int size = countNumList.size();for (Integer count : countNumList) {// 由于countNumList由小到大有序，则每次从左边开始剔除数字，使得最终种类最少// 遍历countNumList，如果k>=当前次数，则直接删除，种类减少1即size--if (k >= count) {k -= count;size--;} else {// 如果k<当前次数，则删除当前次数1次后，总的种类并无变化，所以直接终止for循环，// 不用再继续判断下一个数字了（因为countNumList有序）break;}}return size;}

二、单词直接最短距离

给定一个单词列表arr和word1,word2，求出这两个单词之间的最短距离word1,word2不相等且均在arr列表中

public static int getMinDistance(String[] arr, String word1, String word2) {// 在for循环外定义2个变量，用于存储word1,word2的索引下标,注意要用-1表示，否则会计算出错// 将两者索引下标之差的绝对值进行比较，取最小值（注意pos1和pos2均不为空）int pos1 = -1;int pos2 = -1;int minDistance = Integer.MAX_VALUE;for (int i = 0; i < arr.length; i++) {if (word1.equals(arr[i])) {pos1 = i;} else if (word2.equals(arr[i])) {pos2 = i;}if (pos1 >= 0 && pos2 >= 0) {minDistance = Math.min(minDistance, Math.abs(pos1 - pos2));}}return minDistance;}