目录
题目部分
解读与思路
代码实现
题目部分
题目 | 根据某条件聚类最少交换次数 |
难度 | 难 |
题目说明 | 给出数字K,请输出所有结果小于K的整数组合到一起的最少交换次数。 组合一起是指满足条件的数字相邻,不要求相邻后在数组中的位置。 数据范围 -100 <=K <= 100 -100 <= 数组中数值 <= 100 |
输入描述 | 第一行输入数组:1 3 1 4 0 第二行输入K数值:2 |
输出描述 | 第一行输出最少较好次数:1 |
补充说明 |
小于2的表达式是 1 1 0,共三种可能将所有符合要求数字组合在一起,最少交换1次。 没有数字小于K,即不存在满足条件的数字时,返回 0。 交换规则为,任意两个位置的数字可以相互交换。(笔者注) |
----------------------------------------- | |
示例 | |
示例1 | |
输入 | 1 3 1 4 0 2 |
输出 | 1 |
说明 | 无 |
示例2 | |
输入 | 0 0 0 1 0 2 |
输出 | 0 |
说明 | 无 |
示例3 | |
输入 | 2 3 2 1 |
输出 | 0 |
说明 | 无 |
解读与思路
题目解读:
第一行输入整形数字 K,第二行输入一串整形数字(假设这一串整形数字存放在一个数组中)。
题目要求,从第二行整形数字中,找出所有小于 K 的数字。然后通过交换位置的方式,使找出的这些数字聚合在一块。
- 聚合在一块的意思是,这些数字两两相邻,中间不存在不符合条件(大于或等于K)的数字。
- 交换位置的规则是,数组(根据之前的假设,数字存放在数组中)中的任意两个下标的数字交换都可以交换位置。
在示例 1 中,下标为0的数字 1和下标为3的数字4交换后,数字串变成了 4 3 1 1 0。此时,从第2个元素到第4个元素,这3个数字全都小于2(K等于2)。再次过程中,交换了1次。
特别注意,在示例 3 中,没有数字小于K,即不存在满足条件的数字时,返回 0。
此题立意很好,但在表述上还有很大的提升空间。
题干应该准确描述背景、条件和要求。晦涩难懂或有歧义的题目容易产生误导。示例作用是进一步印证题干的描述,而不应用于补充题目说明。
出题人在描述问题时,部分隐含条件没有描述出来(当找不到满足条件的交换次数时,返回值应该是多少),而且表述不够清晰(应明示交换规则为,任意两个位置的数字可以相互交换),需要结合示例才能准确理解题目意思。
分析与思路:
第一行输入的数字设为 k。
第二行输入的一串数字,把它存到一个整形数组 arr[] 中。
先遍历数组 arr,统计 arr 中小于 k 的数字个数 count,并记录这些数字的最小下标 minIdx 和 最大下标 maxIdx。如果 count 为 0,则直接返回 0。
题目要求小于 k 的数字聚合在一起,那么最终聚合的块的数字是连续的,假设聚合块中数字的最小下标为 iMin,最大小标为 iMax,那么 iMax - iMin == count - 1,且下标在iMin与iMax之间的所有数字都小于 k 。
对于原始数组,如果某个小于 k 的数字,其在 arr 中的下标处于闭区间 [iMin, iMax] 中,那么它不需要交换;如果在此闭区间之外,需要和其他下标在 [ iMin, iMax ] 中且大于 k 的数字交换。显而易见,交换次数为 [iMin, iMax] 这个闭区间(闭区间为arr数组的下标)中大于 k 的数字的个数。
由于 iMin >= minIdx,iMax >= maxIdx,此题的要求可以转换成,从 [minIdx, maxIdx] 这个闭区间中,找出一个长度为 count 的闭区间(闭区间为arr数组的下标),使 arr 数组中大于 k 的数字的个数最小。计算出的最小个数,即为最终的输出。
此算法需要遍历数组两次(第二次只需要遍历 [ minIdx, maxIdx - count ]),其时间复杂度为 O(n)。实现过程中使用了辅助数组用于存储数字,空间复杂度为 O(n)。
代码实现
Java代码
import java.util.Scanner;
/**
* 根据某条件聚类最少交换次数
*
* @since 2023.09.13
* @version 0.2
* @author Frank
*
*/
public class TogetherChgCnt {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
// 第一行输入一串数字,以空格分隔
String stream = sc.nextLine();
String[] strArr = stream.split(" ");
int[] arr = new int[strArr.length];
for (int i = 0; i < strArr.length; i++) {
arr[i] = Integer.parseInt(strArr[i]);
}
// 第二行, k
String strK = sc.nextLine();
int k = Integer.parseInt(strK);
processTogetherChgCnt(k, arr);
}
}
private static void processTogetherChgCnt(int k, int[] arr) {
int minIdx = -1;
int maxIdx = -1;
int count = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= k) {
continue;
}
count++;
if (minIdx == -1) {
minIdx = i;
maxIdx = i;
} else {
maxIdx = i;
}
}
if (count == 0) {
System.out.println(0);
return;
}
int curCnt = 0;
for (int i = 0; i < count; i++) {
if (arr[minIdx + i] >= k) {
curCnt++;
}
}
int rangeCnt = curCnt;
int stepSize = maxIdx - minIdx - count + 1;
// 在区间[ minIdx, maxIdx ]范围内,
// 逐个向右移动,计算移动后的闭区间中大于 k 的个数 curCnt。
for (int i = 0; i < stepSize; i++) {
if (arr[minIdx + i] >= k) {
curCnt--;
}
if (arr[minIdx + count + i] >= k) {
curCnt++;
}
if (curCnt < rangeCnt) {
rangeCnt = curCnt;
}
}
System.out.println(rangeCnt);
}
}
JavaScript代码文章来源:https://www.toymoban.com/news/detail-697754.html
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {
while (line = await readline()) {
// 第一行数据转换成数组
var arr = line.split(" ");
for (var i = 0; i < arr.length; i++) {
arr[i] = parseInt(arr[i]);
}
// 第二行数据,k
line = await readline();
var k = parseInt( line );
processTogetherChgCnt(k, arr);
}
}();
function processTogetherChgCnt(k, arr) {
var minIdx = -1;
var maxIdx = -1;
var count = 0;
for (var i = 0; i < arr.length; i++) {
if (arr[i] >= k) {
continue;
}
count++;
if (minIdx == -1) {
minIdx = i;
maxIdx = i;
} else {
maxIdx = i;
}
}
if (count == 0) {
console.log(0);
return;
}
var curCnt = 0;
for (var i = 0; i < count; i++) {
if (arr[minIdx + i] >= k) {
curCnt++;
}
}
var rangeCnt = curCnt;
var stepSize = maxIdx - minIdx - count + 1;
for (var i = 0; i < stepSize; i++) {
if (arr[minIdx + i] >= k) {
curCnt--;
}
if (arr[minIdx + count + i] >= k) {
curCnt++;
}
if (curCnt < rangeCnt) {
rangeCnt = curCnt;
}
}
console.log(rangeCnt);
}
(完)文章来源地址https://www.toymoban.com/news/detail-697754.html
到了这里,关于华为OD机考算法题:根据某条件聚类最少交换次数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!