注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

火车的家

Put first thing first

 
 
 

日志

 
 

2014.12.25 Duplication in an Array 2  

2014-12-25 23:32:07|  分类: 技术博客 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Attention: 
The content in the article comes from book "Code interview".

Question:
An array contains n numbers ranging from 0 to n-1. There are some numbers duplicated in the
array. It is not clear how many numbers are duplicated or how many times a number gets duplicated. How do you find a duplicated number in the array? For example, if an array of length 7 contains the numbers {2, 3, 1, 0, 2, 5, 3}, the implemented function (or method) should return either 2 or 3.

Answer:
#include <stdlib.h>
#include <stdio.h>

void finddup( int array[], int array_len )
{
    int i = 0;

    for ( i = 0; i < array_len; ++i ) {
        if ( array[i] != i ) {
            // treat the array as a linked list
            int previous = i;
            int next = array[previous];

            while ( 1 ) {
                //the last element may be i, then exit the loop
                if ( next == i ) {
                    array[i] = i;
                    break;
                }

                if ( array[next] == next && next != previous ) {
                    printf( "dup is %d\n", next );
                    return;
                } else {
                    int tmp = array[next];
                    printf("array[%d]=%d\n", next, tmp);

                    array[next] = next;
                    next = tmp;
                    printf("next = %d\n", next);
                }
            }
        }
    }
}

int main(int argc, char* argv[])
{
    int data1[] = {1, 2, 3, 4, 7, 5, 0, 6};

    finddup( data1, sizeof(data1)/sizeof(int) );
}
  评论这张
 
阅读(254)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017