写是为了更好的思考,坚持写作,力争更好的思考。
今天分享两个关于“最小、最短”的算法题,废话少说,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两种整数类型文章来源:https://www.toymoban.com/news/detail-800015.html
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列表中文章来源地址https://www.toymoban.com/news/detail-800015.html
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;
}
到了这里,关于不同整数的最少数目和单词直接最短距离的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!