当前位置： 面试刷题>> 宠物收养所 (经典算法题500道)
### 题目描述补充
**题目：宠物收养所**
宠物收养所管理着多种类型的宠物，每种宠物都有一个唯一的编号和类型（如猫、狗、鸟等）。收养所遵循一个特定的收养规则：每次收养时，收养者可以选择任意一只宠物，但如果收养所中存在与这只宠物类型相同但编号更小的宠物，那么这些编号更小的同类型宠物必须先被收养。如果找不到满足条件的宠物，则可以选择任意一只宠物进行收养。
现在，给定一系列收养请求（每个请求代表一个收养者的选择），请设计一个算法来模拟收养过程，并输出收养顺序。
**输入**：
- 宠物列表：一个包含宠物编号和类型的数组，例如 `[["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
$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 示例代码
```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 示例代码
```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);
```
**码小课**网站中有更多相关内容分享给大家学习，包括算法设计、数据结构、编程技巧等，欢迎访问学习。