3.數(shù)組向左移若干位的算法##
3.1雜技算法
最重要的是如何使用左移位數(shù)和數(shù)組長度的最大公約數(shù)
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.如何快速來轉(zhuǎn)置一個(gè)矩陣？##
作者給出的解答是：為每條記錄插入列號和行號址晕，然后調(diào)用系統(tǒng)的磁帶排序程序先按列排序再按行排序顿锰，最后使用另一個(gè)程序刪除列號和行號。
8.求n個(gè)數(shù)字中最小的k個(gè)元素硼控？##
8.1排序###
先排序，O(nlogn),然后取前k個(gè)O(k), 所以為O(nlogn＋k)
8.2建立一個(gè)大小為k的堆###
先拿前k個(gè)數(shù)建立一個(gè)堆易核，O(k)浪默，再循環(huán)拿剩下的n-k個(gè)數(shù)與堆頂比較，每次維護(hù)為O(logk), 所以為O((n－k)logk＋k)
8.3建立一個(gè)大小為n的堆###
建立大小為n的堆碰逸，O(n)阔加，然后循環(huán)k次，每次取堆頂元素胜榔，O(klogn), 所以為O(n ＋ klogn)
8.4直接維護(hù)一個(gè)大小為k的數(shù)組###
選擇或交換排序，即遍歷n個(gè)數(shù)夭织，先把最先遍歷到的K個(gè)數(shù)存入大小為k的數(shù)組之中，對這k個(gè)數(shù)讲竿，利用選擇或交換排序，找到k個(gè)數(shù)中的最大數(shù)Kmax(Kmax為這K個(gè)元素的數(shù)組中最大的元素)题禀，用時(shí)間為O(k)（你應(yīng)該知道，插入或選擇排序查找操作需要O(k)的時(shí)間）削彬，后再繼續(xù)遍歷后n-k個(gè)數(shù)秀仲，x與Kmax比較：如果x< Kmax，則x代替Kmax，并再次重新找出K個(gè)元素的數(shù)組中的最大元素Kmax'拌消；如果x>Kmax，則不更新數(shù)組墩崩。這樣每次更新和不更新數(shù)組所用的時(shí)間為O(k)或O(0)，整趟下來铝阐，總的時(shí)間復(fù)雜度平均下來為：O(n*k)
