- 最小的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)，比第一种思路要好很多。
总结
这次就到这里了，数组部分后面还会有一篇。不足之处，还请多指教。
