题目描述补充

题目：宠物收养所

宠物收养所管理着多种类型的宠物，每种宠物都有一个唯一的编号和类型（如猫、狗、鸟等）。收养所遵循一个特定的收养规则：每次收养时，收养者可以选择任意一只宠物，但如果收养所中存在与这只宠物类型相同但编号更小的宠物，那么这些编号更小的同类型宠物必须先被收养。如果找不到满足条件的宠物，则可以选择任意一只宠物进行收养。

现在，给定一系列收养请求（每个请求代表一个收养者的选择），请设计一个算法来模拟收养过程，并输出收养顺序。

输入：

• 宠物列表：一个包含宠物编号和类型的数组，例如 [["Dog", 3], ["Cat", 1], ["Dog", 2]]。
• 收养请求列表：一个整数数组，表示收养者选择的宠物编号，例如 [2, 1, 3]。

输出：

• 收养顺序列表：一个整数数组，表示按照收养规则被收养的宠物编号顺序。

示例

输入：

• 宠物列表：[["Dog", 3], ["Cat", 1], ["Dog", 2]]
• 收养请求列表：[2, 1, 3]

输出：

• 收养顺序列表：[1, 2, 3]

解释：

• 第一个收养请求是编号2的宠物，但存在编号更小的同类型宠物（Dog，编号1），因此先收养编号1的Dog。
• 第二个收养请求是编号1的宠物，此时编号1的Dog已被收养，所以直接收养编号1的Cat。
• 第三个收养请求是编号3的宠物，此时没有其他编号更小的同类型宠物，所以收养编号3的Dog。

PHP 示例代码

<?php

function findPetToAdopt($pets, $adoptionRequests) {
    $petMap = [];
    $adoptedOrder = [];

    // 构建宠物类型到编号列表的映射
    foreach ($pets as $pet) {
        $type = $pet[0];
        $id = $pet[1];
        if (!isset($petMap[$type])) {
            $petMap[$type] = [];
        }
        $petMap[$type][] = $id;
    }

    foreach ($adoptionRequests as $requestId) {
        $adopted = false;
        foreach ($petMap as $type => $ids) {
            // 逆序遍历，找到第一个不大于请求编号的宠物
            for ($i = count($ids) - 1; $i >= 0; $i--) {
                if ($ids[$i] <= $requestId) {
                    $adoptedId = array_shift($ids); // 移除已收养的宠物编号
                    $adoptedOrder[] = $adoptedId;
                    $adopted = true;
                    break;
                }
            }
            if ($adopted) {
                break;
            }
        }

        // 如果没有找到符合条件的宠物，则直接收养请求编号的宠物（题目未明确说明此情况，但按逻辑应允许）
        if (!$adopted) {
            // 这里假设所有请求编号都是有效的，实际中可能需要额外处理
            $adoptedOrder[] = $requestId;
        }
    }

    return $adoptedOrder;
}

// 示例用法
$pets = [["Dog", 3], ["Cat", 1], ["Dog", 2]];
$adoptionRequests = [2, 1, 3];
$result = findPetToAdopt($pets, $adoptionRequests);
print_r($result);

?>

Python 示例代码

def find_pet_to_adopt(pets, adoption_requests):
    pet_map = {}
    adopted_order = []

    # 构建宠物类型到编号列表的映射
    for pet in pets:
        type_, id_ = pet
        if type_ not in pet_map:
            pet_map[type_] = []
        pet_map[type_].append(id_)

    for request_id in adoption_requests:
        adopted = False
        for type_ in pet_map:
            # 逆序遍历，找到第一个不大于请求编号的宠物
            for i in range(len(pet_map[type_]) - 1, -1, -1):
                if pet_map[type_][i] <= request_id:
                    adopted_id = pet_map[type_].pop(i)  # 移除已收养的宠物编号
                    adopted_order.append(adopted_id)
                    adopted = True
                    break
            if adopted:
                break

        # 如果没有找到符合条件的宠物，则直接收养请求编号的宠物（假设所有请求编号都有效）
        if not adopted:
            adopted_order.append(request_id)

    return adopted_order

# 示例用法
pets = [["Dog", 3], ["Cat", 1], ["Dog", 2]]
adoption_requests = [2, 1, 3]
result = find_pet_to_adopt(pets, adoption_requests)
print(result)

JavaScript 示例代码

function findPetToAdopt(pets, adoptionRequests) {
    const petMap = {};
    const adoptedOrder = [];

    // 构建宠物类型到编号列表的映射
    pets.forEach(pet => {
        const [type, id] = pet;
        if (!petMap[type]) {
            petMap[type] = [];
        }
        petMap[type].push(id);
    });

    adoptionRequests.forEach(requestId => {
        let adopted = false;
        for (const type in petMap) {
            // 逆序遍历，找到第一个不大于请求编号的宠物
            for (let i = petMap[type].length - 1; i >= 0; i--) {
                if (petMap[type][i] <= requestId) {
                    const adoptedId = petMap[type].splice(i, 1)[0]; // 移除已收养的宠物编号
                    adoptedOrder.push(adoptedId);
                    adopted = true;
                    break;
                }
            }
            if (adopted) {
                break;
            }
        }

        // 如果没有找到符合条件的宠物，则直接收养请求编号的宠物（假设所有请求编号都有效）
        if (!adopted) {
            adoptedOrder.push(requestId);
        }
    });

    return adoptedOrder;
}

// 示例用法
const pets = [["Dog", 3], ["Cat", 1], ["Dog", 2]];
const adoptionRequests = [2, 1, 3];
const result = findPetToAdopt(pets, adoptionRequests);
console.log(result);

码小课网站中有更多相关内容分享给大家学习，包括算法设计、数据结构、编程技巧等，欢迎访问学习。