题面描述

在本题中，要求实现一个动态内存管理模块的内存块合并功能。当用户释放一组内存块（如“2,4,3,7,6”）后，系统需返回当前最大的连续可用内存块的起始编号和长度。如果多个最大连续内存块存在，需返回起始编号最小的那个。通过对释放的内存块进行排序和合并，最终输出一个包含起始位置和长度的元组（例如“2,3”），表示从编号2开始的长度为3的连续内存块是最大的。

思路

由于需要我们查找连续数字,因此,我们需要对给定的数组进行排序,这样我们判断两个数字连续只需要判断$arr[i]-arr[i-1]==1$即可.

那么我们可以对于每一个数字$arr[i]$都以它本身编号i为起始编号,不断向后查找求得最长长度,时间复杂度为$O(n^2)$.这个时间复杂度可以优化.我们发现假设i为起始编号对应最长长度为$cnt(cnt>1)$,那么$i+1$为起始编号时,最长长度肯定是$cnt-1$.

因此,我们一旦发现最长长度$cnt$大于1时,那么后续的$cnt-1$个数都不需要寻找最长长度,因为必定小于$cnt$.

按照上面的思路,我们假设$i$为起始编号时,对应最长长度为$cnt$.此时,下一步我们需要判断的下标就可以为$i+cnt$,其中$[i+1,i+cnt-1]$的下标都不需要判断最长长度.所以总的时间复杂度为$O(n)$,因为每个点都只会被所有循环加起来枚举到一次.

题解

在本题中，我们需要实现一个动态内存管理模块的内存块合并功能。当用户释放一组内存块编号时，我们需要返回当前最大的连续可用内存块的起始编号和长度。为了实现这一点，我们可以按照以下步骤进行：

1. 输入处理：首先读取用户输入的内存块编号，并将其拆分成整数数组。

2. 排序：对数组进行排序，以便后续判断相邻编号是否连续。

3. 查找最大连续块：

   • 遍历排序后的数组，通过判断相邻元素的差值是否为1来确定连续的内存块。
   • 记录当前连续块的长度，并更新最大连续块的信息（起始编号和长度）。
   • 优化查找过程：当我们发现一个连续块的长度大于1时，后续的连续块长度必定小于之前的长度，因此可以跳过已检查的元素，直接移动到下一个可能的起始位置。

4. 输出结果：最终输出找到的最大连续内存块的起始编号和长度。

代码

CPP

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> arr; // 存储释放的内存块编号
    std::string input; // 用于存储输入字符串
    std::getline(std::cin, input); // 读取整行输入

    std::string token; // 用于存储分割的每个编号
    size_t pos = 0; // 记录当前分割位置
    // 处理输入，将以逗号分隔的数字转为整数并存入数组
    while ((pos = input.find(',')) != std::string::npos) {
        token = input.substr(0, pos); // 提取当前编号
        arr.push_back(std::stoi(token)); // 转换为整数并存入数组
        input.erase(0, pos + 1); // 移除已处理的部分
    }
    arr.push_back(std::stoi(input)); // 处理最后一个编号

    std::sort(arr.begin(), arr.end()); // 对数组进行排序

    int i = 0; // 当前遍历的索引
    int ans1 = -1; // 用于存储最大连续块的起始编号
    int ans2 = -1; // 用于存储最大连续块的长度

    while (i < arr.size()) { // 遍历整个数组
        int cnt = 1; // 记录当前连续块的长度
        // 向后查找相邻的连续数字
        for (int j = i + 1; j < arr.size(); j++) {
            // 判断相邻元素是否连续
            if (arr[j] - arr[j - 1] == 1) {
                cnt++; // 如果连续，长度加1
            } else {
                break; // 如果不连续，退出循环
            }
        }
        // 更新最大连续块的信息
        if (cnt > ans2) { // 如果当前长度大于已知最大长度
            ans2 = cnt; // 更新最大长度
            ans1 = arr[i]; // 更新起始编号
        }
        // 跳过已经检查的元素，直接移动到下一个可能的起始位置
        i += cnt; // 将i移动到下一个待检查的索引
    }
    
    // 输出结果，格式为“起始编号,长度”
    std::cout << ans1 << ",";
    std::cout << ans2 << std::endl;
    
    return 0; // 返回成功
}

python

arr = [int(i) for i in input().split(",")]#处理输入
arr.sort()#排序
i = 0
ans1 = -1
ans2 = -1
while i < len(arr):#第一层循环
    cnt = 1
    for j in range(i + 1, len(arr)):#记录最大相邻数
       if arr[j] - arr[j - 1] == 1:#向后找有没有相邻的
           cnt += 1
       else:
           break
    if cnt > ans2:#更新答案
        ans2 = cnt
        ans1 = arr[i]
    i += cnt#按照题解意思,我们后面需要查找的下标为i+cnt
print(ans1,end="")
print(",",end="")
print(ans2,end="")

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(",");
        List<Integer> arr = new ArrayList<>();
        for (String s : input) {
            arr.add(Integer.parseInt(s));
        }//处理输入
        Collections.sort(arr);//排序

        int i = 0;
        int ans1 = -1;
        int ans2 = -1;
        while (i < arr.size()) {//第一层循环
            int cnt = 1;
            for (int j = i + 1; j < arr.size(); j++) {//记录最大相邻数
                if (arr.get(j) - arr.get(j - 1) == 1) {//向后找有没有相邻的
                    cnt++;
                } else {
                    break;
                }
            }
            if (cnt > ans2) {//更新答案
                ans2 = cnt;
                ans1 = arr.get(i);
            }
            i += cnt;//按照题解意思,我们后面需要查找的下标为i+cnt
        }
        System.out.print(ans1 + ",");
        System.out.print(ans2);
    }
}

Go

package main

import (
	"fmt"
	"sort"
	"strconv"
	"strings"
)

func main() {
	var input string
    fmt.Scanln(&input)
	arrStr := strings.Split(input, ",")
	arr := make([]int, len(arrStr))
	for i, numStr := range arrStr {
		arr[i], _ = strconv.Atoi(numStr)
	}//处理输入

	sort.Ints(arr)//排序
	i := 0
	ans1 := -1
	ans2 := -1
	for i < len(arr) {//第一层循环
		cnt := 1
		for j := i + 1; j < len(arr); j++ {//记录最大相邻数
			if arr[j]-arr[j-1] == 1 {//向后找有没有相邻的
				cnt++
			} else {
				break
			}
		}
		if cnt > ans2 {//更新答案
			ans2 = cnt
			ans1 = arr[i]
		}
		i += cnt//按照题解意思,我们后面需要查找的下标为i+cnt
	}
	fmt.Printf("%d,%d", ans1, ans2)
}

Js

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.question('', input => {
  const arr = input.split(',').map(Number);//处理输入
  arr.sort((a, b) => a - b);//排序

  let i = 0;
  let ans1 = -1;
  let ans2 = -1;
  while (i < arr.length) {//第一层循环
    let cnt = 1;
    for (let j = i + 1; j < arr.length; j++) {//记录最大相邻数
      if (arr[j] - arr[j - 1] === 1) {//向后找有没有相邻的
        cnt++;
      } else {
        break;
      }
    }
    if (cnt > ans2) {//更新答案
      ans2 = cnt;
      ans1 = arr[i];
    }
    i += cnt;//按照题解意思,我们后面需要查找的下标为i+cnt
  }
  console.log(`${ans1},${ans2}`);

  rl.close();
});

题目描述

小明最近对在开发一个简单的操作系统，今天他的任务是为操作系统的动态内存管理模块实现内存块的合并功能。

介绍一下操作系统的内存管理模块:操作系统的动态内存管理模块是操作系统中非常重要的一部分，其主要功能是在程序运行时动态地分配和释放内存。动态内存管理模块根据程序的内存需求，调用物理内存管理模块，对内存进行分配或者释放。为了使得内存的分配更加高效，动态内存管理模块通常会实现内存池的机制。内存池就是一个预先分配好一定数量的内存块的集合，程序运行时可以从内存池中获取内存块，而不必动态地去分配内存空间。这样可以极大地提高内存分配的速度。动态内存管理模块还负责内存的回收和整理。当程序不再使用某些内存空间时，动态内存管理模块将这些空间标记为可回收空间，并把它们加入内存释放队列。在适当的时候，动态内存管理模块就会回收这些空间，并重新整理内存空间，以便留出更大的连续内存块来给后续的内存分配操作使用。"

小明考虑这个模块可以根据用户需求分配任意大小的内存块，并在用户释放内存时将其回收到内存池中以供其他用户使用，他把这个任务安排给了小G同学。小G同学需要设计并实现这个回收合并模块，这个模块在每次释放内存块后返回当前最大的连续内存块的起始位置和长度。如果存在多个最大连续内存块，返回起始位置最小的内存块。

输入描述

输入是一组释放的内存块编号，用逗号分隔。例如，输入 "$1,3,2,5$" 表示释放了四个内存块，它们的编号分别为 $1、3、2$ 和 $5$。每个内存块的大小为 $1$ 个单位。请注意，函数执行前所有内存块都已被申请完毕，没有空闲内存块。不需要考虑重复释放内存块。

内存块编号: $0$ $\leq$ 编号 $\leq$ $2^{31} - 1$

单词释放的内存块个数 $\leq$ $10000$

输出描述

输出是一个由两个整数组成的元组，表示经过回收处理后当前可用的最大连续内存块的起始编号和长度。例如，输出 "$1,3$" 表示合并后的连续内存块的起始编号是 $1$，长度为 $3$。如果存在多个最大连续内存块，则返回起始编号最小的那个。

样例1

输入：

2,4,3,7,6

输出

2,3

解释

$2 ,4, 3, 7 ,6$ 表示释放了 $5$ 块内存，内存块编号分别为 $2, 4, 3 ,7, 6$ .

经过回收合并后，$2,3,4$ 三块内存连续，可以合并为一块大内存、大小为 $3$ 个单位

$6 ,7$ 两块内存连续，合并后连续内存大小为 $2$ 。

因此返回此时的最大连续内存的起始位置为 $2$ ，内存大小为 $3$

样例2

输入

1,3,7,9,8,6

输出

6,4