zzzrf：给定一个有 n 个对象（包括 k 种不同的颜色，并按照 1 到 k 进行编号）的数组，将对象进行分类使相同颜色的对象相邻，并按照 1,2，...k 的顺序进行排序。
- 不能使用代码库中的排序函数来解决这个问题
- k <= n
在线做题地址
样例 1
输入:
[3,2,2,1,4]
4
输出:
[1,2,2,3,4]
样例 2
输入:
[2,1,1,2,2]
2
输出:
[1,1,2,2,2]
算法一：分治法
运使用 rainbowSort，或者说是改动过的 quickSort，运用的是分治的思想，不断将当前需要处理的序列分成两个更小的序列处理。
算法思路
- 思路与 quickSort 大致相同，每次选定一个中间的颜色，这个中间的颜色用给出的 k 来决定，将小于等于中间的颜色的就放到左边，大于中间颜色的就放到右边，然后分别再递归左右两半。
代码思路
- 递归函数设置四个参数，序列需要处理区间的左右端点和处理的颜色区间
- 根据给定的颜色区间决定中间的颜色
- 将小于等于中间的颜色的就放到左边，大于中间颜色的就放到右边
- 递归左右两半，直到颜色区间长度等于 1
复杂度分析
N 为序列长度，K 为颜色数
- 空间复杂度：O(1)
- 时间复杂度：O(NlogK)
- 每次是对 K 分成左右进行递归，因此有 logK 层，每层递归遍历到整个序列，长度为 N
public class Solution {
/*
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
public void sortColors2(int[] colors, int k) {
if (colors == null || colors.length < 2) {
return;
}
sort(colors, 0, colors.length - 1, 1, k);
}
private void sort(int[] colors, int start, int end, int colorFrom, int colorTo) {
//若处理区间长度为小于等于 1 或颜色区间长度为 1，则不需要再进行处理
if (start >= end || colorFrom == colorTo) {
return;
}
//设置左右指针以及中间的颜色
int left = start;
int right = end;
int colorMid = colorFrom + (colorTo - colorFrom) / 2;
while (left <= right) {
//找到左侧大于中间颜色的位置
while (left <= right && colors[left] <= colorMid) {
left++;
}
//找到右侧小于等于中间颜色的位置
while (left <= right && colors[right] > colorMid) {
right--;
}
//交换左右指针指向的颜色
if (left <= right) {
int temp = colors[left];
colors[left] = colors[right];
colors[right] = temp;
}
}
//继续递归处理左右两半序列
sort(colors, start, right, colorFrom, colorMid);
sort(colors, left, end, colorMid + 1, colorTo);
}
}
算法二：计数排序（ counting sort ）
- 题目要求不使用额外的数组，一种方法是使用彩虹排序(rainbow sort)，但是这样虽然做到了没有使用额外的空间，但是代价是时间复杂度变成了 O(N logK)，那么是否有方法做到时间和空间的双赢呢？
- 我们重新考虑计数排序(counting sort)，这里我们需要注意到颜色肯定是 1-k，那么 k 一定小于 n，我们是否可以用 colors 自己本身这个数组作为 count 数组呢？
- 下面我们介绍一种不占用大量额外空间的计数排序的写法。
算法思路
- 我们用负数代表数字出现的次数，例如 colors[i]=-cnt 表示数字 i 出现了 cnt 次
代码思路
- 我们从左往右遍历 colors 数组
- 若 colors[i] > 0 且 colors[colors[i]] < 0，那么 colors[colors[i]] -= 1
- 若 colors[i] > 0 且 colors[colors[i]] > 0，那么先用临时变量 temp 存下 colors[i],将 colors[colors[i]]赋值给 colors[i]，再将 colors[temp] = -1
注意此时 i 指针并不需要指向下一个位置，因为交换过来的值还未进行计数
- 若 colors[i] < 0，跳过
- 倒着输出每种颜色
- 另外注意数组下标是从 0 开始，为了避免 n==k 导致数组越界的情况，本题中 colors[i]对应的计数位为 colors[colors[i] - 1]
复杂度分析
NN 表示 colors 数组长度
- 空间复杂度：O(1)
- 时间复杂度：O(N)
public class Solution {
/**
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
public void sortColors2(int[] colors, int k) {
int len = colors.length;
if(len <= 0) {
return;
}
int index = 0;
while(index < len) {
int temp = colors[index] - 1;
//遇到计数位，跳过
if(colors[index] <= 0){
index++;
}
else {
//已经作为计数位
if(colors[temp] <= 0) {
colors[temp]--;
colors[index] = 0;
index++;
}
//还未被作为计数位使用
else {
swap(colors[index], colors[temp]);
colors[temp] = -1;
}
}
}
//倒着输出
int i = len - 1;
while(k > 0) {
for(int j = 0; j>colors[k-1]; j--) {
colors[i--] = k;
}
k--;
}
}
public void swap(int[] colors , int a , int b){
int temp = colors[a];
colors[a] = colors[b];
colors[b] = temp;
return ;
}
}
题目地址 https://leetcode.com/problems/sort-colors/description/ 题目描述 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are …
通过List <int>在函数参数中传递超过10个lac记录？ - c#我遇到的情况是数据库中有10多个lac记录。当用户使用某些选定的记录在MVC中点击我的操作方法时，我想通过获取所有记录并将它们与用户传递的记录进行比较来检查这些记录是否存在于数据库中。然后我想将所有这些记录传递给另一个函数。在函数参数中传递这么多记录是否安全？这是一个演示：- //Action Method [HttpGet] Public ActionRe…
怎么撸三个数据类型的集合ligiggy：基于 C#，需要建立一个数量大概在几百的，为<int,string,string>的集合，目前的想法有如下两种： Tuple<int,string,string>很好实现，但是可读性很差 采用面对对象的思想，建立三个对应属性，然后用数组将数据结合起来 想知道，还有没有其他更好的办法
在PHP中使用long int - php我正在尝试此方法，但无法存储较大的价值$var = rand(100000000000000,999999999999999); echo $var; // prints a 9 digit value(largest possible) 如何获得期望值？ 参考方案 PHP整数通常为32位。其他软件包提供了更高精度的整数：http://php.net/man…
C＃Linq可空INT字段包含在List <int>中SQL转换 - c#我有一张表格，其中列出了需要管理员签名的表单，而我想要做的就是将表单列表过滤到他们可以签名的表单。我得到了他们所管理的员工列表，然后将其放入员工ID列表中。var staffIds = manager.Staff.Select(x => x.Id).ToList(); 然后，我使用人员列表过滤表单列表。我得到了所有与经过身份验证的组织ID相匹配的表单，…