sitinspring(http://www.blogjava.net)原创,转载请注明出处.博客访问： 327547
博文数量： 134
博客积分： 2071
博客等级： 大尉
技术积分： 1460
注册时间：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
原文地址： 作者：
来自互联网，有改动。
问题：数组a[N]，1至N-1这N-1个数存放在a[N]中，其中某个数重复一次。写一个函数，找出被重复的数字。时间复杂度不超过O(n)。
一、数学推导法
不重复时 sum = 1+2+...+ d + (d+1)...+N；现在less =&1+2+...+ d + d +&(d+1)+...+(N-1)。
sum 和 less都有N个数，由于less中只有一个重复的数字d，则必有1 <= d
sum - less = 0+0+...+ 0 + (-d) + 0...0 + N = ( N - d )&。所以重复的d = N - (sum - less)。
二、标志数组法
设数组a[n] = {2,3,2,1}，2是重复数字。
把一个数组b[]初始化为"0000"，对a[]访问一位在b[]上标记一位，再次访问到时查看标志位已经被置1则发现重复。空间复杂度O(n)。&
遍历时，a[0]=2，令b[2]=1，"0010"；a[1]=3，令b[3]=1，"0011"；a[2]=2，b[2]已经==1，找到a[2]。
int do_dup(int arr[],int NUM)
&&&&&&&&int i = 0;
&&&&&&&&int *arrayflag = malloc( NUM * sizeof(int) );
&&&&&&&&while(i++ < NUM)
&&&&&&&&&&&&&&&&arrayflag[i] = 0;
&&&&&&&&for(i=0; i<NUM; i++)
&&&&&&&&&&&&&&&&if( 0 == arrayflag[ arr[i] ] )
&&&&&&&&&&&&&&&&&&&&&&&arrayflag[arr[i]] = 1; // 置出现标志
&&&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&free(arrayflag);
&&&&&&& return arr[i];
三、固定偏移标志法
同样是访问过后做标记的思想，为克服申请了O(n)的空间的缺陷，充分利用a[N]本身值和下标的关系来做标记，把标记直接放到数组内的数值上再清除标记。时间O(n)=N，空间O(n)=1。
a[N]，里面是1至N-1。原数组a[i]最大是N-1，若a[i]=K在某处出现后，将a[K]加一次N，做标记，当某处a[i]=K再次成立时，查看a[K]即可知道K已经出现过。a[i]在程序中最大也只是N-1+N=2N-1。注意防止值溢出。
以数组{2,3,1,2}为例。所谓固定偏移，有点间接寻址的意思 :)。
a[0]=2 < 4，未标记，K=2，&&& a[2]=1 < 4，做标记，让a[2]= a[2]+4 = 5；&&&&&&&&&&&&&&&&&&&&&&&&&& a[1]=3 < 4，未标记，K=3，&&& a[3]=2 = 4，还原K=a[2]-4=1，a[1]=3 = 5，还原K=a[3]-4=2, a[2]=5 >=4，不能还原，发现重复，返回a[3]=2。
下边的实现可能改变了原数组，需要恢复处理。
int do_dup(int arr[], int NUM)
&&&&int i, k = 0;
&&&&for(i=0; i<NUM; ++i)
&&&&&&&&// get new index K
&&&&&&&&if(arr[i] >= NUM)
&&&&&&&&&&&&K = arr[i] - NUM; //has marked, recover
&&&&&&&&else
&&&&&&&&&&&&K = arr[i];
&&&&&&&&// mark or duplicate
&&&&&&&&if(arr[K] < NUM)
&&&&&&&&&&&&arr[K] += NUM; // mark it
&&&&&&&&else
&&&&&&&&&&&&printf("got duplicate %d.\n", a[i]);
&&&&&&&&&&&&return a[i];
四、既然利用a[N]本身值和下标的关系，可以用访问的结果K作为要标记数的索引，那么就不仅可以用NUM来标记和还原，还能更变态地使用int数据类型的符号位来标记，数据本身是正数，不影响数据的标记和恢复。
bool dup(int array[],int n)
&&&&&for(int i=0;i<n;i++)
&&&&&&&&&if(array[i]>0) //可以以此作下标去判断其他值
&&&&&&&&&{
&&&&&&&&&&&&&&&if(array[array[i]]<0)
&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&&return array[i];//已经被标上负值了，有重复
&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&&array[array[i]]= －array[array[i]]; //否则标记为负
&&&&&&&&&&&&&&&&}
&&&&&&&&&}
&&&&&&&&&else // |array[i]|代表的值已经出现过一次了
&&&&&&&&&{
&&&&&&&&&&&&&&&if(array[-array[i]]<0)
&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&return -array[i];//有重复
&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&array[-array[i]]=－array[-array[i]];
&&&&&&&&&&&&&&&}
&&&&&&&&&&}
&&&&&&return -1;//没有重复
//用于修复数组
void restorearray(int array[],int n)
&&&&&&&&for(int i=0;i<n;i++)
&&&&&&&&&&&&&&&&if(array[i]<0)array[i]= －array[i];
但是上述问题并不能处理一般的数组中的重复数字，如问题2。
问题2：有一个数组t[100]，存放了int型的正整数（若含有负数呢？），用效率较高的算法把重复数字去掉。例如数组{1,2,2,6,3,5,6,6}变成{1,2,3,5,6}。
每次读一个元素就先在HashMap里面find，如果找到，就跳过这个数。如果没有找到,则在HashMap里面insert这个数，并且把这个数加入到要返回的数组中。会额外的使用一块HashMap的内存。
阅读(11835) | 评论(0) | 转发(0) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。[java实现]找一个数组的最大和的连续子数组(时间复杂度 O(n)) - 决心1119 - 博客园
收藏一下，请直接点击原帖地址：
这是《剑指Offer》中的一道题目，数组中的元素可能是正负，所以连续的子组求和，会变大也可能变小，解题时首先要求当前的和（初始值为0）和下一个元素求和后，如果是负的，那么重新置0和下下个继续求和，首先要找到使和增加的正的元素。然后有了当前最大的和后，纪录下来；继续累加求和，若新增的元素使和变为负数，那么重新置0，按这个逻辑找出剩余元素的一个最大子组和，若超过前纪录，覆盖，直到子组遍历结束。（动态规划解题方法就是首先想好整个事件发展的逻辑，比如Sn和Sn－1，Sn－2的关系，然后可以用递归思想，或者数学上的归纳法得到事件发展规律，但是动态规划不同于递归的高复杂度的开销，它将有用的子结果纪录到表中，以部分空间来节约时间）下面代码为置顶链接的原帖作者的代码。
public class FindMaxSumOfSubArray {
public static void main(String[] args) {
FindMaxSumOfSubArray f = new FindMaxSumOfSubArray();
int[] arr = { 1, -2, 3, 10, -4, 7, 2, -5 };
System.out.println("MaxSum:" + f.findMaxSum(arr));
public Integer findMaxSum(int[] arr) {
int curSum = 0;
int maxSum = 0;
int len = arr.
if (arr == null || len == 0) {
return null;
for (int i = 0; i & i++) {
curSum += arr[i];
if (curSum & 0) {
curSum = 0;
if (curSum & maxSum) {
maxSum = curS
if (maxSum == 0) {
for (int i = 0; i & i++) {
if (i == 0) {
maxSum = arr[i];
if (arr[i] & maxSum) {
maxSum = arr[i];
return maxS}