实验要求:有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示,其中h是这个人的身高,k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。 如输入[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]],要求输出:[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]。
时间: 2023-08-18 22:29:59 浏览: 130
这道题可以使用贪心算法来解决。我们可以先对原始队列按照身高h从高到低排序,如果身高h相等,则按照k从小到大排序。之后我们按照k的值插入到新队列中,由于k表示排在这个人前面且身高大于或等于h的人数,那么插入时,我们只需要考虑比当前人身高高的人数即可。
具体地,我们按照上述规则排序后,从身高最高的人开始插入到新队列中。由于当前人的身高最高,所以他的k值即为他在新队列中的位置。之后按照身高递减的顺序,依次插入到新队列中,按照当前人的k值,插入到对应的位置即可。由于每次插入操作都只涉及到当前人的身高和k值,所以时间复杂度为O(nlogn)。
程序代码实现如下:
```python
def reconstructQueue(people: List[List[int]]) -> List[List[int]]:
# 按照身高从高到低排序,如果身高相等,则按照k从小到大排序
people.sort(key=lambda x: (-x[0], x[1]))
# 依次插入到新队列中
res = []
for p in people:
res.insert(p[1], p)
return res
```
这个算法的时间复杂度是O(nlogn),空间复杂度是O(n)。
相关问题
java输出一个由n个整数组成的数组打乱重拍后字典序最小的数组
在 Java 中,为了生成一个由 n 个整数随机组成的数组,并保证其字典序是最小的,你需要遵循以下步骤:
1. 首先,创建一个包含 n 个整数的数组。例如,`int[] arr = new int[n];`
2. 由于需要保证字典序最小,你需要对这 n 个整数范围进行排序(比如从0到某个最大值),然后随机选择其中的元素填充数组。可以使用 `Random` 类的 `nextInt()` 方法生成随机数。
3. 使用 `Collections.shuffle()` 函数来打乱数组的顺序。这个函数会随机地改变数组中元素的相对位置,保持原始范围内元素不变。
4. 确保在打乱之前先按照字典序排列一次,这样即使打乱后也能确保字典序尽可能小。
这是一个简单的示例代码片段:
```java
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
public class Main {
public static void main(String[] args) {
int n = 5; // 可根据需要自定义数组长度
int maxNum = 100; // 数组内元素的最大值
Random random = new Random();
// 生成并排序数组
int[] sortedArr = generateSortedArray(n, maxNum);
System.out.println("Original sorted array: " + Arrays.toString(sortedArr));
// 打乱数组顺序
Collections.shuffle(Arrays.asList(sortedArr));
// 输出打乱后的数组
System.out.println("Shuffled and minimum dictionary order array: " + Arrays.toString(sortedArr));
}
private static int[] generateSortedArray(int n, int maxNum) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = random.nextInt(maxNum); // 生成随机数并填入数组
}
Arrays.sort(arr); // 排序
return arr;
}
}
```
c语言输入一个三位整数打乱顺序求
它的最大值和最小值,你能给我一个实现的思路吗?
好的,针对您的问题,我可以给您提供一种简单的思路。您可以将输入的三位整数分解成个位、十位和百位上的数字,然后将这些数字进行排序,从而得到这个三位整数的最小值和最大值。具体实现方式可以使用数组和循环来完成。如果您需要更具体的代码实现,可以告诉我,我会给您提供更详细的帮助。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)