求整形数组中满足两数之和为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;
}