问题描述小明是唐门年轻一代的暗器高手他正在练习唐门绝技“暴雨梨花针”。每次发射可以覆盖一排连续的敌人但每次发射都会消耗一枚银针。敌人排成一行每个敌人都有一个特定的编号可能重复。小明发现除了一个编号的敌人需要被单独针对外其他编号的敌人都是成对出现的即每个编号恰好有两个敌人。为了节省银针小明希望用最少的发射次数消灭所有敌人每次发射可以消灭任意连续的一段敌人但要求这段中不能包含两个相同编号的敌人即同一编号的两个敌人不能被同一发银针消灭。注意每次发射后被消灭的敌人将不再存在后续发射只能针对剩余的敌人。你的任务是帮助小明计算最少需要多少次发射才能消灭所有敌人。要求设计一个算法计算最少发射次数。时间复杂度应为 O(n)其中 n 是敌人的数量。测试样例样例1输入enemies [1, 2, 1, 3, 2]输出2解释编号1和2的敌人都成对出现。第一次发射消灭前两个敌人[1,2]此时剩余敌人为[1,3,2]。第二次发射消灭剩余所有敌人[1,3,2]注意这次发射中没有重复编号。不能一次发射消灭所有敌人因为第一个和第三个敌人编号相同1不能在同一发中消灭。样例2输入enemies [5, 5, 3, 3, 4]输出3解释编号5和3的敌人都成对出现编号4的敌人单独出现。第一次发射消灭第一个敌人[5]此时剩余敌人为[5,3,3,4]。第二次发射消灭第二个和第三个敌人[5,3]此时剩余敌人为[3,4]。第三次发射消灭最后两个敌人[3,4]。每次发射中都没有重复编号。样例3输入enemies [1, 2, 3, 2, 1, 3, 4]输出2解释编号1、2、3的敌人都成对出现编号4的敌人单独出现。第一次发射消灭前四个敌人[1,2,3,2]注意这段中没有重复编号编号2虽然出现两次但位置不同且编号2的两次出现不在同一发射段。剩余敌人为[1,3,4]。第二次发射消灭剩余所有敌人[1,3,4]没有重复编号。约束条件1 ≤ enemies.length ≤ 1000001 ≤ enemies[i] ≤ 100000敌人数量为奇数除了一个编号的敌人出现一次外其余每个编号的敌人都恰好出现两次程序代码#include stdio.h#include string.hint minShots(int* enemies, int enemiesSize) {int first[100001], second[100001];memset(first, -1, sizeof(first));memset(second, -1, sizeof(second));for (int i 0; i enemiesSize; i) {int id enemies[i];if (first[id] -1) {first[id] i;} else {second[id] i;}}// 收集区间 [first, second]int intervals[50000][2];int cnt 0;for (int id 1; id 100000; id) {if (first[id] ! -1 second[id] ! -1) {intervals[cnt][0] first[id];intervals[cnt][1] second[id];cnt;}}// 如果没有成对的区间只有独特元素需要1次发射if (cnt 0) {return 1;}// 按左端点排序冒泡排序因为cnt最多50000但实际数据规模不大for (int i 0; i cnt - 1; i) {for (int j i 1; j cnt; j) {if (intervals[i][0] intervals[j][0]) {int tmp0 intervals[i][0], tmp1 intervals[i][1];intervals[i][0] intervals[j][0];intervals[i][1] intervals[j][1];intervals[j][0] tmp0;intervals[j][1] tmp1;}}}// 合并重叠区间int mergedCnt 0;for (int i 0; i cnt; i) {int l intervals[i][0];int r intervals[i][1];if (mergedCnt 0) {intervals[mergedCnt][0] l;intervals[mergedCnt][1] r;mergedCnt;} else if (l intervals[mergedCnt - 1][1]) {// 重叠合并if (r intervals[mergedCnt - 1][1]) {intervals[mergedCnt - 1][1] r;}} else {// 不重叠新区间intervals[mergedCnt][0] l;intervals[mergedCnt][1] r;mergedCnt;}}// 最少发射次数 合并区间数 1return mergedCnt 1;}int main() {int enemies1[] {1, 2, 1, 3, 2};int enemies2[] {5, 5, 3, 3, 4};int enemies3[] {1, 2, 3, 2, 1, 3, 4};printf(%d\n, minShots(enemies1, 5)); // 2printf(%d\n, minShots(enemies2, 5)); // 3printf(%d\n, minShots(enemies3, 7)); // 2return 0;}#include stdio.h #include string.h int minShots(int* enemies, int enemiesSize) { int first[100001], second[100001]; memset(first, -1, sizeof(first)); memset(second, -1, sizeof(second)); for (int i 0; i enemiesSize; i) { int id enemies[i]; if (first[id] -1) { first[id] i; } else { second[id] i; } } // 收集区间 [first, second] int intervals[50000][2]; int cnt 0; for (int id 1; id 100000; id) { if (first[id] ! -1 second[id] ! -1) { intervals[cnt][0] first[id]; intervals[cnt][1] second[id]; cnt; } } // 如果没有成对的区间只有独特元素需要1次发射 if (cnt 0) { return 1; } // 按左端点排序冒泡排序因为cnt最多50000但实际数据规模不大 for (int i 0; i cnt - 1; i) { for (int j i 1; j cnt; j) { if (intervals[i][0] intervals[j][0]) { int tmp0 intervals[i][0], tmp1 intervals[i][1]; intervals[i][0] intervals[j][0]; intervals[i][1] intervals[j][1]; intervals[j][0] tmp0; intervals[j][1] tmp1; } } } // 合并重叠区间 int mergedCnt 0; for (int i 0; i cnt; i) { int l intervals[i][0]; int r intervals[i][1]; if (mergedCnt 0) { intervals[mergedCnt][0] l; intervals[mergedCnt][1] r; mergedCnt; } else if (l intervals[mergedCnt - 1][1]) { // 重叠合并 if (r intervals[mergedCnt - 1][1]) { intervals[mergedCnt - 1][1] r; } } else { // 不重叠新区间 intervals[mergedCnt][0] l; intervals[mergedCnt][1] r; mergedCnt; } } // 最少发射次数 合并区间数 1 return mergedCnt 1; } int main() { int enemies1[] {1, 2, 1, 3, 2}; int enemies2[] {5, 5, 3, 3, 4}; int enemies3[] {1, 2, 3, 2, 1, 3, 4}; printf(%d\n, minShots(enemies1, 5)); // 2 printf(%d\n, minShots(enemies2, 5)); // 3 printf(%d\n, minShots(enemies3, 7)); // 2 return 0; }运行结果