3.数组向左移若干位的算法##
3.1杂技算法
最重要的是如何使用左移位数和数组长度的最大公约数
void func(int *arr, int rotdist, int length)
{
int max=gcd(rotdist, length);//!!!!!!!!!!!!!
for(int i=0; i<max; i++)//!!!!!!!!!!!!!!!!!!
{
int temp=arr[i];
int to=i;
int from=(to+rotdist)%length;
while(from != i)
{
arr[to]=arr[from];
to= from;
from =(to+rotdist)%length;
}
arr[to]=temp;
}
return;
}
3.2reverse###
reverse(0, n1-1);
reverse(n1, n2-1);
reverse(0, n2-1);
7.如何快速来转置一个矩阵？##
作者给出的解答是：为每条记录插入列号和行号，然后调用系统的磁带排序程序先按列排序再按行排序，最后使用另一个程序删除列号和行号。
8.求n个数字中最小的k个元素？##
8.1排序###
先排序，O(nlogn),然后取前k个O(k), 所以为O(nlogn＋k)
8.2建立一个大小为k的堆###
先拿前k个数建立一个堆，O(k)，再循环拿剩下的n-k个数与堆顶比较，每次维护为O(logk), 所以为O((n－k)logk＋k)
8.3建立一个大小为n的堆###
建立大小为n的堆，O(n)，然后循环k次，每次取堆顶元素，O(klogn), 所以为O(n ＋ klogn)
8.4直接维护一个大小为k的数组###
选择或交换排序，即遍历n个数，先把最先遍历到的K个数存入大小为k的数组之中，对这k个数，利用选择或交换排序，找到k个数中的最大数Kmax(Kmax为这K个元素的数组中最大的元素)，用时间为O(k)（你应该知道，插入或选择排序查找操作需要O(k)的时间），后再继续遍历后n-k个数，x与Kmax比较：如果x< Kmax，则x代替Kmax，并再次重新找出K个元素的数组中的最大元素Kmax'；如果x>Kmax，则不更新数组。这样每次更新和不更新数组所用的时间为O(k)或O(0)，整趟下来，总的时间复杂度平均下来为：O(n*k)
