珠海网站建设公,查询网站有没有备案,手机网站建设设计服务,深圳网络市场推广写是为了更好的思考#xff0c;坚持写作#xff0c;力争更好的思考。 今天分享两个关于“最小、最短”的算法题#xff0c;废话少说#xff0c;show me your code#xff01;
一、不同整数的最少数目 给你一个整数数组arr和一个整数k。现需要从数组中恰好移除k个元素坚持写作力争更好的思考。 今天分享两个关于“最小、最短”的算法题废话少说show me your code
一、不同整数的最少数目 给你一个整数数组arr和一个整数k。现需要从数组中恰好移除k个元素请找出移除后数组中不同整数的最少数目 输入 arr[5,4,5],k1 输出1 解释 移除1个4数组中只剩下5一种整数 输入 arr[4,3,1,1,3,3,2],k3 输出2 解释先移除4,2然后再移除两个1中任意1个1或者移除两个3中的任意1个3最后剩余1和3两种整数类型 public static int getMinDifference(int[] arr, int k) {// key存放数组数字value存放次数MapInteger, Integer map new HashMap();for (int i : arr) {map.put(i, map.getOrDefault(i, 0) 1);}// 对次数按照自然顺序排序即由小到大ListInteger 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;}
