1.给你一个数组，求一个k值，使得前k个数的方差 + 后面n-k个数的方差最小 ，时间复杂度可以到O(n)。
根据方差公式D(X)=E(x^2)-[E(X)]^2
def minVariance(arr): sum=0 square_sum=0 length=len(arr) left_var=[0]*length right_var=[0]*length
#从左到右求每一段的方差 for i in range(length): sum+=arr[i] square_sum+=arr[i]*arr[i] left_var[i]=square_sum/(i+1)-(sum/(i+1))**2
sum = 0 square_sum = 0
#从右到左求每一段的方差 for j in range(length-1,-1,-1): sum+=arr[j] square_sum += arr[j] * arr[j] right_var[j] = square_sum / (length-j) - (sum / (length-j)) ** 2
#二者合并，找出方差最小的两断 index=0 variance=left_var[0]+right_var[0] for k in range(length-1): if left_var[k]+right_var[k+1]<variance: variance=left_var[k]+right_var[k] index=k+1 return index
2.给你一个只由0和1组成的字符串，找一个最长的子串，要求这个子串里面0和1的数目相等。 时间复杂度可以到O(n)
这样一种巧妙的解法：定义一个数据B[N]， B[i]表示从A[0...i]中 num_of_0 - num_of_1，0的个数与1的个数的差。 那么如果arr[i] ~ arr[j]是符合条件的子串，一定有 B[i] == B[j]，因为中间的部分0、1个数相等，相减等于0。 只需要扫一遍A[N]就能把B[N]构造出来了。
def findMaxEqualSequence(arr): count=[0,0] B=[0]*len(arr) dict_num={} curlen=0 maxlen=0 for i in range(len(arr)): count[arr[i]]+=1
#数组B保存到当前i下标这一段中0出现的次数与1出现的次数之差 B[i]=count[0]-count[1]
#如果到当前下标差值等于0，说明从开始到现在两者出现次数是一样的，当前下标+1就是满足要求最长子串的长度，直接continue下一个就行了 if B[i]==0: maxlen=i+1
continue
#将差值第一次出现都保存在字典里面，以后每次计算一个差值都访问一下字典，如果字典中有，说明字典保存的下标到当前下标这一段，出现0与1
#的个数是相等的，然后计算两者下标之差，与maxlen做比较即可。 if dict_num.__contains__(B[i]): curlen=i-dict_num[B[i]] if curlen>maxlen: maxlen=curlen
#字典中没有说明该差值第一次出现，就记录在字典中 else: dict_num[B[i]]=i return maxlen
3.给你一个数组，求一个数组的最大值和次大值
def getMaxAndNextMax(arr): max_val=arr[0] next_val=arr[0] for k in arr: if k>max_val: next_val=max_val max_val=k elif k>next_val: next_val=k return(max_val,next_val) a=[-2.5,4,300,3,1000,8,100] print(getMaxAndNextMax(a))
4.给定一个n个整型元素的数组a，其中有一个元素出现次数超过n / 2，求这个元素。据说是百度的一道题
方法一：对数组进行排序，因为一个元素已经超过了一半，则中间位置的元素就必为该元素。
方法二：火拼方法。
来看这样一个例子：
5 1 5 4 1 1 3 1 2 1 1
一共11个数字，其中1一共出现了6次。那么如何快速的找到这个6呢？我们来考虑这样一个现实生活中的例子：有一群人在打群架，他们每个人有一个编号，代表自己所处的势力，现在这一群人按照顺序依次往广场中央走，如果广场内现在有和自己不是一个势力的人，那么他就和其中一个同归于尽，问，最后哪一个势力的人会获胜？我们按照这个意思，再来看一下刚才这个例子：
1）势力5的一个人走进广场中央，现在广场中央有一个人，势力是5
2）势力1的一个人走进广场中央，他发现广场中央有一个势力是5的人，于是同归于尽，现在广场上没有人
3）势力5的一个人走进广场中央，现在广场中央有一个人，势力是5
4）势力4的一个人走进广场中央，他发现广场中央有一个势力是5的人，于是同归于尽，现在广场上没有人
5）势力1的一个人走进广场中央，现在广场有一个人，势力是1
6）势力1的一个人走进广场中央，现在广场有两个人，势力是2
……
可以发现，每一次火拼，势力最大（也就是出现次数最多的那个数字）的那个每次最多只会死亡一个。而火拼最多会进行N/2次，出现频率最高的那个数字最多只会损失N/2个，而题上告诉我们出现次数已经超过了一半，因此广场上剩下的那个团伙的编号必然是出现次数做多的那个！这样一来，代码就非常好写了。
def getAppearMoreThanHalf(arr): curVal=arr[0] count=1 for i in range(1,len(arr)): if count==0: curVal=arr[i] count=1 continue if arr[i]==curVal: count+=1 else: count-=1 return curVal a=[3,5,7,7,7] print(getAppearMoreThanHalf(a))
5.求数组中元素的最短距离
题目：给定一个含有n个元素的数组，找出数组中的两个元素X和Y使得abs（x-y）最小
解题思路：先排序，然后遍历元素。
6.求两个有序数组的共同元素
充分利用数组有序的性质，用两个指针i和j分别指向a和b，比较a[i]和b[j]，根据比较结果移动指针，则有如下三种情况
1. a[i] < b[j]，则i增加1，继续比较
2. a[i] == b[j]，则i和j皆加1，继续比较
3. a[i] < b[j]，则j加1，继续比较
重复以上过程直到i或j到达数组末尾。
小小总结一下，对于在数组中进行查找的问题，可以分如下两种情况处理
1. 如果给定的数组有序，那么首先应该想到Binary Search，所需O(logn)
2. 如果给定的数组无序，那么首先应该想到对数组进行排序，很多排序算法都能在O(nlogn)时间内对数组进行排序，然后再使用二分搜索，总的时间复杂度仍是O(nlogn)。
如果能做到以上两点，大多数关于数组的查找问题，都能迎刃而解。
7.求数组中满足给定和的数对
题目：给定两个有序整型数组a和b，各有n个元素，求两个数组中满足给定和的数对，即对a中元素i和b中元素j，满足i + j = d(d已知)
解析：两个指针i和j分别指向数组的首尾，然后从两端同时向中间遍历。
// 找出满足给定和的数对
void FixedSum(int* a, int* b, int n, int d)
{
for (int i = 0, j = n - 1; i < n && j >= 0)
{
if (a[i] + b[j] < d)
++i ;
else if (a[i] + b[j] == d)
{
cout << a[i] << ", " << b[j] << endl ;
++i ;
--j ;
}
else // a[i] + b[j] > d
--j ;
}
}
8.字符串逆序
题目：给定一个含有n个元素的字符数组a，将其原地逆序（不能额外开辟空间）。
def strReverse(s): left=0 right=len(s)-1 while left<right: s[left],s[right]=s[right],s[left] left+=1 right-=1 return s s="abcde" print(strReverse(s))
9.数组元素重排问题
给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求：
1. 排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变
2. 不能使用额外存储空间
例子如下
输入 0, 3, 0, 2, 1, 0, 0
输出 0, 0, 0, 0, 3, 2, 1
解析：从尾部开始设置两个指针，last指针指向后面第一个出现0的位置，first指向last前面的第一个非0元素，如果first是非0，则将值赋给last，然后last++，first++；如果first指向0，则继续前进first++。
def Arrange(arr): length=len(arr) first=length-1 last=length-1
#last从后面找到第一个0元素位置 if arr[last]!=0: while last>=0 and arr[last]!=0: last-=1 if last<0: return first=last-1 #这个时候开始遍历走 while first>=0: if arr[first]!=0: arr[first],arr[last]=arr[last],arr[first] first-=1 last-=1 else: first-=1 return arr a=[6,0,3,0,2,1,0,0] print(Arrange(a))
10.找出绝对值最小的元素
题目：给定一个有序整数序列（非递减序），可能包含负数，找出其中绝对值最小的元素，比如给定序列 -5, -3, -1, 2, 8 则返回1。
解析：
- 如果给定的序列中所有的数都是正数，那么数组的第一个元素即是结果。
- 如果给定的序列中所有的数都是负数，那么数组的最后一个元素即是结果。
- 如果给定的序列中既有正数又有负数，那么绝对值得最小值一定出现在正数和负数的连接处
def findAbsoluteMinVal(arr): if arr[0]>0: return arr[0] if arr[len(arr)-1]<0: return arr[len(arr)-1] for i in range(1,len(arr)): if arr[i]>0: return arr[i] if abs(arr[i-1])>arr[i] else abs(arr[i-1])
11.two sum(leetcode题目一)
未排序数组，找出两个元素值等于target值，并返回下标，小的下标在前面。
def twoSum(self, nums, target): if len(nums)<1: return dict={} for i in range(len(nums)): if target-nums[i] in dict: return (dict[target-nums[i]],i) else: dict[nums[i]]=i