求整形數(shù)組中滿足兩數(shù)之和為sum的數(shù)值對(duì)
1. 最直觀的想法是兩個(gè)for循環(huán)遍歷兩數(shù)之和 如果有=sum 輸出 。O(n^2)
2. 如果
先排序，則會(huì)簡(jiǎn)單很多
排序后 用兩個(gè)指針指ij向數(shù)組頭尾 然后頭尾相加 >sum則j-- <sum則i++ O(NlogN+N/2)
3. 排序 然后設(shè)b=sum-a[i] 然后二分查找b O(NlogN+NlogN)
大概如此 關(guān)鍵在于 排序使問(wèn)題變得很簡(jiǎn)單 復(fù)雜度從N^2下降到NlogN了
ref.
http://blog.csdn.net/hopestar2/article/details/4658669發(fā)帖水王
思路1：排序->一次遍歷知最大次數(shù) O(NlogN)
思路2：
數(shù)組中有個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)了數(shù)組長(zhǎng)度的一半。也就是說(shuō)，
有個(gè)數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)次數(shù)的和還要多。因此我們可以考慮在遍歷數(shù)組的時(shí)候保存兩個(gè)值：一個(gè)是數(shù)組中的一個(gè)數(shù)字，一個(gè)是次數(shù)。當(dāng)我們遍歷到下一個(gè)數(shù)字的時(shí)候，如果下一個(gè)數(shù)字和我們之前保存的數(shù)字相同，則次數(shù)加1。如果下一個(gè)數(shù)字和我們之前保存的數(shù)字不同，則次數(shù)減1。如果次數(shù)為零，我們需要保存下一個(gè)數(shù)字，并把次數(shù)設(shè)為1。由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)之和還要多，那么要找的數(shù)字肯定是最后一次把次數(shù)設(shè)為1時(shí)對(duì)應(yīng)的數(shù)字。O(N)!!
ref.
http://hc6900.blog.163.com/blog/static/11666002720112296329410/
第一個(gè)只出現(xiàn)一次的字符
沒(méi)有思路的思路：對(duì)數(shù)組每個(gè)元素 遍歷數(shù)組 記錄它出現(xiàn)的次數(shù) >1則continue O(N^2)
思路1：由于是字符 所以可以按照ascii排序 然后遍歷之 O(NlogN+N)
思路2：HASH 先
建一HASH表 每個(gè)acsii為1個(gè)key 然后遍歷以記錄各字符的次數(shù) 然后遍歷尋找最大值 O(N+N)
ref.
http://zhedahht.blog.163.com/blog/static/25411174200722191722430/
O(lgN)時(shí)間內(nèi)找出有序數(shù)組中某個(gè)元素出現(xiàn)的次數(shù)
既然數(shù)組已然有序 那么最直接的想法就是遍歷 但時(shí)間復(fù)雜度為O(N)
若要O(lgN) 那應(yīng)該想到
二叉樹(shù)！！ 于是 binary_search找到指定元素，然后左右查詢，得到出現(xiàn)的次數(shù)k，但其時(shí)間復(fù)雜度為O(lgn)+k。
可通過(guò)改進(jìn)binary_search，做兩次查找，一次得到指定元素的起始出現(xiàn)位置，一次得到終止出現(xiàn)位置。
ref.
http://blog.csdn.net/yysdsyl/article/details/5419482
大數(shù)相加
思路:存為數(shù)組然后對(duì)位相加
tmpSum=a[i]+b[i];
sum[i]+=tmpSum%10;
sum[i+1]+=tmpSum/10;
今天被人人網(wǎng)電面的一個(gè)題目:
字符串?dāng)?shù)組 去掉空格
期待回答: 遞歸之
遇到這種題 一定不可以妄想先把空格標(biāo)識(shí)出來(lái)再做處理
而每次遇到空格都把后面所有向前挪也是不可取的
思路2: 遍歷過(guò)程中每次遇到一個(gè)空格 就把后面第一個(gè)不是空格的元素挪到空格的位置 繼續(xù)
遞歸和非遞歸思路如下:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#define STR "ab c efg "
void No_recurse(char *STR)
{
char *p=NULL, *q=NULL, *tmp=NULL;
for (p=STR,q=STR; *p!='\0'; p++)
{
if (*p==' '||*p=='\t')
continue;
if (p!=q)
{
*q = *p;
*p = ' ';
}
q++;
}
*q='\0';
//printf("%s\n", STR);
}
void Recurse(char *p, char *q)
{
if (*p == '\0')
{
*q = '\0';
return;
}
if (*p==' '||*p=='\t')
{
Recurse(p+1, q);
return;
}
if (p!=q)
{
*q = *p;
*p = ' ';
}
Recurse(p+1, q+1);
return;
}
int main()
{
char STR[20]= "ab c efg ";
Recurse(STR, STR);
//No_recurse(STR);
printf("%s\n", STR);
return 0;
}