求整形數組中滿足兩數之和為sum的數值對
1. 最直觀的想法是兩個for循環遍歷兩數之和 如果有=sum 輸出 。O(n^2)
2. 如果
先排序，則會簡單很多
排序后 用兩個指針指ij向數組頭尾 然后頭尾相加 >sum則j-- <sum則i++ O(NlogN+N/2)
3. 排序 然后設b=sum-a[i] 然后二分查找b O(NlogN+NlogN)
大概如此 關鍵在于 排序使問題變得很簡單 復雜度從N^2下降到NlogN了
ref.
http://blog.csdn.net/hopestar2/article/details/4658669發帖水王
思路1：排序->一次遍歷知最大次數 O(NlogN)
思路2：
數組中有個數字出現的次數超過了數組長度的一半。也就是說，
有個數字出現的次數比其他所有數字出現次數的和還要多。因此我們可以考慮在遍歷數組的時候保存兩個值：一個是數組中的一個數字，一個是次數。當我們遍歷到下一個數字的時候，如果下一個數字和我們之前保存的數字相同，則次數加1。如果下一個數字和我們之前保存的數字不同，則次數減1。如果次數為零，我們需要保存下一個數字，并把次數設為1。由于我們要找的數字出現的次數比其他所有數字出現的次數之和還要多，那么要找的數字肯定是最后一次把次數設為1時對應的數字。O(N)!!
ref.
http://hc6900.blog.163.com/blog/static/11666002720112296329410/
第一個只出現一次的字符
沒有思路的思路：對數組每個元素 遍歷數組 記錄它出現的次數 >1則continue O(N^2)
思路1：由于是字符 所以可以按照ascii排序 然后遍歷之 O(NlogN+N)
思路2：HASH 先
建一HASH表 每個acsii為1個key 然后遍歷以記錄各字符的次數 然后遍歷尋找最大值 O(N+N)
ref.
http://zhedahht.blog.163.com/blog/static/25411174200722191722430/
O(lgN)時間內找出有序數組中某個元素出現的次數
既然數組已然有序 那么最直接的想法就是遍歷 但時間復雜度為O(N)
若要O(lgN) 那應該想到
二叉樹！！ 于是 binary_search找到指定元素，然后左右查詢，得到出現的次數k，但其時間復雜度為O(lgn)+k。
可通過改進binary_search，做兩次查找，一次得到指定元素的起始出現位置，一次得到終止出現位置。
ref.
http://blog.csdn.net/yysdsyl/article/details/5419482
大數相加
思路:存為數組然后對位相加
tmpSum=a[i]+b[i];
sum[i]+=tmpSum%10;
sum[i+1]+=tmpSum/10;
今天被人人網電面的一個題目:
字符串數組 去掉空格
期待回答: 遞歸之
遇到這種題 一定不可以妄想先把空格標識出來再做處理
而每次遇到空格都把后面所有向前挪也是不可取的
思路2: 遍歷過程中每次遇到一個空格 就把后面第一個不是空格的元素挪到空格的位置 繼續
遞歸和非遞歸思路如下:
#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;
}