算法-数组（三）

• 最小的k个数
• 求子数组的最大和
• 把数组排成最小的数字

1.最小的k个数

问题描述：输入n个数字，找到数组中最小的k个数。例如输入4,5,1,6,2,7,3,8这8个数字，最小的4个数字就是1,2,3,4。

算法思想

思路一：我们可能会有这样一个思路，先对数组进行排序，这样找最小的k个数字就简单多了，但是排序的时间复杂度是O(nlogn)。我们可以尝试快速排序的思路，快速排序是每次找到一个数字，对数组中的数字，比这个数字小的排在前面，比这个数字大的排在后面。那么我们如果针对第k个数字进行调整，比这个数字小的排前面，比这个数字大的排后面，那么最后排在前面的k个数字就是我们要找的数字了，这个算法的时间复杂度是O(n).

这样的思路我们需要清楚两点：首先，这个算法会改变原来数组的顺序，因为本来就是基于快速排序的。其次，我们最后得到的这k个数字是无序的。

思路二：时间复杂度为O(nlogk)的算法。
我们先定义好一个长度为k个容器，每次从输入的数组中选择一个数字填入这个容器中，如果容器没有满，那么直接将读到的数字填入其中，如果容器满了，那么从容器中选择最大的数字，和这个数字比较，如果它比读到的数字大，就替换掉这个最大的数字，否则就读下一个。

当容器满了之后，我们需要做3件事情，第一，找到容器中最大的数字；第二，有可能删除这个最大的数字；第三，可能插入一个数字。

如果我们用二叉树实现这个容器，那么我们能在O(logk)内完成这3步操作。对于n个输入的数字而言，时间复杂度就是O(nlogn)。我们可以用不同的数据结构实现这个二叉树，比如说大顶堆，这样我们能在O(1)时间内找到最大的数字，但是删除和插入结点还是需要O(logk)。也可以借助红黑树来实现。这里只写了个思路，有兴趣的同学可以自己尝试一下。

在提一点，这一种思路很适合处理海量数据，它不会改变原数组的顺序，每次读入一个数字，当原数据很大的时候，不能完全加载如内存，每次读取一个数字就很有优势，所以对于n很大，而k很小的时候，这一种思路更好。

代码

这里实现的思路一的代码，后面有时间我再补上思路二的代码。

//交换a,b两个指针指向元素的位置
void Swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

//找最后一个数字进行比较,比它小的排前面，比它大的排后面
int Partition(int *data, int length, int start, int end)
{
    if (data == NULL || length < 0 || start < 0 ||
        end >= length)
    {
        fprintf(stderr, "Invalid parameter.\n");
        exit(1);
    }

    int small = start - 1;//small下标要比start小

    for (int index = start; index < end; index++)
    {
        if (data[index] < data[end])//比它小的放前面
        {
            small++;
            if (small != index)
                Swap(&data[small], &data[index]);
        }
    }
    Swap(&data[++small], &data[end]);
    return small;//返回分割点，start~small是<=data[end]的数
}

//基于快速排序思路的算法
/*data :输入的数组  length：输入数组的长度
  output:输出数组   k：最小的k个数
*/
void GetLeastNumbers_1(int data[], int length, int *output, int k)
{
    if(data == NULL || output == NULL || length <= 0 
    || k <= 0 || k > length)
    {
        fprintf(stderr, "Invalid parameter!\n");
        exit(1);
    }
    int start = 0;
    int end = length - 1;
    int index = Partition(data, length, start, end);//找到分割点
    while (index != k -1)
    {
        if (index < k - 1)
            start = index + 1;
        esle
            end = index - 1;
    
        index = Partition(data, length, start, end);
    }

    for (int i = 0; i < k; i++)
    {
    output[i] = data[i];
    }
}

其实看了上面的代码我们会发现，这个算法并不是绝对的O(n)的时间复杂度，可以确定的是Partition函数的时间复杂度为O(n)，计算分割点时，我们可以发现，如果分割点不是k-1，那么还需要下一次计算，最坏的情况下，如果k大于length/2,且每次计算的index只是递增1，那么时间复杂度就会增加到O(n^2),基于快速排序的的算法时间复杂度受选取的这个数字的影响很大，如果这个数字恰好就是第k大的数字，那么我们能在O(n)内解决这个问题。

2.求子数组的最大和

问题描述：输入一个整数数组，数组中有正数也有负数，数组中连续的一个或多个数字组成该数组的子数组，求子数组的最大和。例如：数组{1,-2,3,10,-4,7,2,-5},最大子数组是{3,10,-4,7,2},和是18.

算法思想

思路一：我们分析一下这个数组找到子数组的最大和过程。step1，step2，我们加上数字1和-2，得到当前的和是-1；step3，定位到3，这是之前的和是-1，加上3之后是2，还小于3，所以之前的和就舍弃，直接从3开始往后加；step4,继续加10，和为13；step5，遇到-4，加上-4之后，和是-9，反而变小了，这里我们需要保存一下13，可能它就是最大的和；step6，遇到7，这时和是9+7=16，比13大，修改这个保存的值；step7，遇到2，此时和为16+2=18，修改保存的值；step8，遇到-5，和变成了13，所以舍弃这个数字，最后的结果是18.

总结一下，就是在加下一个数字的时候，保存下当前的最大和，当之前计算的和是负数的时候，做一下处理，直接舍弃，从当前数字开始计算。

思路二：用动态规划法的思路来解决问题，动态规划法的思想就是将问题分解问多个子问题求解，由子问题的解得到问题的解，与分治法不同的是，它的子问题之间不是独立的，当前子问题的解需要借助上一次求解的结果，这就是我们说的重叠子问题。

分析题目我们可以得到递归公式，公式中的f(i)表示当前计算得到的和，那么max(f(i))就是我们要找的子数组的最大和。

递归公式

我们基于循环来实现动态规划法，其实和上面的算法的代码是一样的，只是分析思路不同而已。

代码

//计算子数组的最大和
int FindGreatestSumOfSubArray(int data[], int length)
{
    if (data == NULL || length <= 0)
    {
        fprintf(stderr, "Invalid parameter!\n");
        exit(1);
    }

    int currentSum = 0;
    //greatest初始化为数组中的数字，否则当数组全是负数的时候就会出错
    int greastSum = data[0];
    for (int i = 0; i < length; i++)
    {
        if (currentSum < 0)
            currentSum = data[i];
        else
            currentSum += data[i];//在上一次求和的基础上加上当前的数字
        if(currentSum > greastSum)
            greastSum = currentSum;
    }
    return greastSum;
}

3.把数组排成最小的数字

问题描述：输入一个整数数组，将数组中的数字拼接，排成一个数字，打印出所能排出的最小的数字。例如，数组{3,32,321}，则这三个数字排出的数字中最小的数字是321323.

算法思想：

思路一：遇到这个题，我们可能会想到字符串的全排列，在之前的算法系列的文章中有提到过，如果找出其全排列，再比较得到最小的，那么时间复杂度为O(n!)，这样的算法思想明显是不好的。
思路二:考虑另一种思路，将数组排成最小的数字，其实就是找到一个排序规则，假如有n,m两个数字，可以排成nm,mn，我们需要考虑是nm这样的顺序数字小还是mn这样的顺序得到的数字小，这里的比较规则不再是n和m哪个数字小， 而是比较组合之后的结果哪个更小,如果是针对数字进行这样的比较，我们需要从数字的最高位一位一位比较。

接下来考虑拼接数字n和m是int型数据，但是不能保证nm还是int型的，也许拼接之后它就超出了int的表示范围，而题目也没有要求我们返回一个数字，所以，可以考虑将数字转换为字符串表示，这样我们就可以使用字符串的拼接函数了和比较函数，而不用针对数字的每一位进行比较，这样会简单许多。

由以上分析得出思路：先将整数数组转换为字符串，然后定义比较函数，对字符串进行排序，最后输出字符串，其中比较函数是关键（定义比较函数时要注意，字符串n和m的比较结果和nm和mn的比较结果是有很大差异的）。

代码

代码中可以直接使用系统的排序函数，c语言中是qsort。由于我个人更熟悉Java，这里用了Java实现，直接调用了Java中的排序函数。

//用MyArray调用静态方法
public class MyArray {

    public static void printMinNumber(int numbers[]) {
        if(numbers == null)
            return;
        //将整数数组转换为字符串
        String[] strNumbers = new String[numbers.length];
        for(int i = 0; i < numbers.length; i++) {
            strNumbers[i] = String.valueOf(numbers[i]);
        }
    
        //调用排序算法TimSort
        Arrays.sort(strNumbers, new StringCompator());
    
        System.out.println(getString(strNumbers));
    }

    //将字符串数字转为字符串
    private static String getString(String strs[]) {
        StringBuilder sBuilder = new StringBuilder();
        for (String str : strs){
            sBuilder.append(str);
        }
        return sBuilder.toString();
    }   
}

定义比较器。

public class StringCompator implements Comparator<String> {

    @Override
    public int compare(String str1, String str2) {
        String temp1 = new String(str1);
        String temp2 = new String(str2);
    
        temp1 = temp1.concat(str2);
        temp2 = temp2.concat(str1);
        //比较组合之后的字符串的大小
        return temp1.compareTo(temp2);
    }
}

时间复杂度分析：由于我使用了Java实现，Java7之后，内置的排序函数就默认为TimSort，它是归并排序和插入排序的组合，在待排数组有一定顺序的情况下，可以达到O(n)的时间复杂度，在随机的情况下也可以达到O(nlogn)，所以最后的时间复杂度是O(nlogn)，比第一种思路要好很多。

总结

这次就到这里了，数组部分后面还会有一篇。不足之处，还请多指教。