目錄

題目部分

解讀與思路

代碼實(shí)現(xiàn)

題目部分

解讀與思路

題目解讀：

第一行輸入整形數(shù)字 K，第二行輸入一串整形數(shù)字（假設(shè)這一串整形數(shù)字存放在一個(gè)數(shù)組中）。

題目要求，從第二行整形數(shù)字中，找出所有小于 K 的數(shù)字。然后通過交換位置的方式，使找出的這些數(shù)字聚合在一塊。

• 聚合在一塊的意思是，這些數(shù)字兩兩相鄰，中間不存在不符合條件（大于或等于K）的數(shù)字。
• 交換位置的規(guī)則是，數(shù)組（根據(jù)之前的假設(shè)，數(shù)字存放在數(shù)組中）中的任意兩個(gè)下標(biāo)的數(shù)字交換都可以交換位置。

在示例 1 中，下標(biāo)為0的數(shù)字 1和下標(biāo)為3的數(shù)字4交換后，數(shù)字串變成了 4?3 1 1?0。此時(shí)，從第2個(gè)元素到第4個(gè)元素，這3個(gè)數(shù)字全都小于2（K等于2）。再次過程中，交換了1次。

特別注意，在示例 3 中，沒有數(shù)字小于K，即不存在滿足條件的數(shù)字時(shí)，返回 0。

此題立意很好，但在表述上還有很大的提升空間。
題干應(yīng)該準(zhǔn)確描述背景、條件和要求?；逎y懂或有歧義的題目容易產(chǎn)生誤導(dǎo)。示例作用是進(jìn)一步印證題干的描述，而不應(yīng)用于補(bǔ)充題目說明。
出題人在描述問題時(shí)，部分隱含條件沒有描述出來（當(dāng)找不到滿足條件的交換次數(shù)時(shí)，返回值應(yīng)該是多少），而且表述不夠清晰（應(yīng)明示交換規(guī)則為，任意兩個(gè)位置的數(shù)字可以相互交換），需要結(jié)合示例才能準(zhǔn)確理解題目意思。

分析與思路：

第一行輸入的數(shù)字設(shè)為 k。
第二行輸入的一串?dāng)?shù)字，把它存到一個(gè)整形數(shù)組 arr[] 中。

先遍歷數(shù)組 arr，統(tǒng)計(jì)?arr 中小于 k 的數(shù)字個(gè)數(shù) count，并記錄這些數(shù)字的最小下標(biāo) minIdx 和 最大下標(biāo) maxIdx。如果 count 為 0，則直接返回 0。

題目要求小于 k 的數(shù)字聚合在一起，那么最終聚合的塊的數(shù)字是連續(xù)的，假設(shè)聚合塊中數(shù)字的最小下標(biāo)為 iMin，最大小標(biāo)為 iMax，那么 iMax?- iMin == count -?1，且下標(biāo)在iMin與iMax之間的所有數(shù)字都小于 k 。

對(duì)于原始數(shù)組，如果某個(gè)小于 k 的數(shù)字，其在 arr 中的下標(biāo)處于閉區(qū)間?[iMin,?iMax] 中，那么它不需要交換；如果在此閉區(qū)間之外，需要和其他下標(biāo)在 [ iMin,?iMax ] 中且大于 k 的數(shù)字交換。顯而易見，交換次數(shù)為 [iMin, iMax] 這個(gè)閉區(qū)間（閉區(qū)間為arr數(shù)組的下標(biāo)）中大于 k 的數(shù)字的個(gè)數(shù)。

由于 iMin >= minIdx，iMax >= maxIdx，此題的要求可以轉(zhuǎn)換成，從 [minIdx, maxIdx] 這個(gè)閉區(qū)間中，找出一個(gè)長(zhǎng)度為 count 的閉區(qū)間（閉區(qū)間為arr數(shù)組的下標(biāo)），使 arr 數(shù)組中大于 k 的數(shù)字的個(gè)數(shù)最小。計(jì)算出的最小個(gè)數(shù)，即為最終的輸出。

此算法需要遍歷數(shù)組兩次（第二次只需要遍歷 [ minIdx, maxIdx - count ]），其時(shí)間復(fù)雜度為 O(n)。實(shí)現(xiàn)過程中使用了輔助數(shù)組用于存儲(chǔ)數(shù)字，空間復(fù)雜度為 O(n)。

代碼實(shí)現(xiàn)

Java代碼

import java.util.Scanner;

/**
 * 根據(jù)某條件聚類最少交換次數(shù)
 * 
 * @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()) {
			// 第一行輸入一串?dāng)?shù)字，以空格分隔
			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;
		// 在區(qū)間[ minIdx, maxIdx ]范圍內(nèi)，
		// 逐個(gè)向右移動(dòng)，計(jì)算移動(dòng)后的閉區(qū)間中大于 k 的個(gè)數(shù) 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代碼

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()) {
        // 第一行數(shù)據(jù)轉(zhuǎn)換成數(shù)組
        var arr = line.split(" ");
        for (var i = 0; i < arr.length; i++) {
            arr[i] = parseInt(arr[i]);
        }
        // 第二行數(shù)據(jù),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);
}

(完)文章來源地址http://www.zghlxwxcb.cn/news/detail-697754.html

到了這里，關(guān)于華為OD機(jī)考算法題：根據(jù)某條件聚類最少交換次數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！