LintCode 题解丨谷歌高频题:两个排序数组的中位数排颜色 II

给定一个有n个对象(包括k种不同的颜色,并按照1到k进行编号)的数组,将对象进行分类使相同颜色的对象相邻,并按照1,2,...k的顺序进行排序。

不能使用代码库中的排序函数来解决这个问题
​k​ <= ​n​
在线评测地址:LintCode 领扣

样例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 ;
}

}
更多题解参考:

九章算法 - 帮助更多中国人找到好工作,硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧

上一篇:大厂面试真题详解:字符串解码


下一篇:大厂面试真题详解:数据流滑动窗口平均值