C语言 数组中重复的数字分析及方法

C语言 数组中重复的数字解决方法:

题目:在一个长度为n的数组里的所有数字都在0-n-1的 范围内。数组中某些数字是重复的,但是不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3.

解法1:对于数组进行排序,之后对于已经排序的数组进行遍历便可知道数组中重复的数字。

时间复杂度;O(nlogn);

解法2:建立一个大小为O(N)的哈希表,遍历数组中的元素并判断是否存在于哈希表中。若不存在于哈希表中,将这个元素加入哈希表之中并且继续扫描,若这个元素存在于哈希表中,则:找到了数组中重复的一个数字;

时间复杂度:O(N),空间复杂度:O(N);

解法3:对于给定的数组进行重排。对于下标为i的元素:如果a[i] == i,扫描下一个元素;如果不相等将a[i]与a[a[i]]进行比较,若是相等则找到了一个重复的数字,若没有,那么对于数字进行交换,依次进行。

int DuplicateInArray(int arr[],int size)
{
  int i=0;
  while(i<size)
  {
    if(arr[i] == i)
      ++i;
    else
    {
      if(arr[i] != arr[arr[i]])
      {swap(arr[i],arr[arr[i]]);}
      else
      {return arr[i];}
    }
  }
  return -1;
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

时间: 2017-03-18

简单分析C语言中指针数组与数组指针的区别

首先来分别看一下,指针数组的一个小例子: #include <stdio.h> #include <string.h> int lookup_keyword(const char*key, const char* table[], const int size) { int ret = -1; int i = 0; for(i=0; i<size; i++) { if (strcmp(key, table[i]) == 0) { ret = i; break; } } ret

详解C语言中Char型指针数组与字符数组的区别

详解C语言中Char型指针数组与字符数组的区别 1.char 类型的指针数组:每个元素都指向一个字符串,指向可以改变 char *name[3] = { "abc", "def", "gbk" }; for(int i = 0 ; i < strlen(name); i ++){ printf("%s\n", *(name+i)); //printf("%s\n", name[i]); } //指向改

C语言二维数组中的查找的实例

C语言二维数组中的查找的实例 题目描述:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数 思路描述:一个数字的下方和右方是比它本身大的区域,而左方和上方时比它本身小的区域.选取右上角的数字进行比较,当该数大于指定的数时,舍去该列,当该数小于指定的数时,舍去该行,当相等时,则表示找到 C语言实现: #include<stdio.h> #include<stdlib.h>

C语言数据结构之顺序数组的实现

C语言数据结构之顺序数组的实现 以下为展示顺序数组的示例: 1.用C语言实现的版本 #include<stdio.h> /* EOF(=^Z或F6),NULL */ #include<math.h> /* floor(),ceil(),abs() */ #include<stdlib.h> /*申请和释放内存*/ #include<stdarg.h> /*可变参数*/ #define OK 1 //成功标志 #define ERROR 0 //错误标志 #d

C语言 数组指针详解及示例代码

数组(Array)是一系列具有相同类型的数据的集合,每一份数据叫做一个数组元素(Element).数组中的所有元素在内存中是连续排列的,整个数组占用的是一块内存.以int arr[] = { 99, 15, 100, 888, 252 };为例,该数组在内存中的分布如下图所示: 定义数组时,要给出数组名和数组长度,数组名可以认为是一个指针,它指向数组的第 0 个元素.在C语言中,我们将第 0 个元素的地址称为数组的首地址.以上面的数组为例,下图是 arr 的指向: 下面的例子演示了如何以指针的方

C语言 指针数组详解及示例代码

如果一个数组中的所有元素保存的都是指针,那么我们就称它为指针数组.指针数组的定义形式一般为: dataType *arrayName[length]; [ ]的优先级高于*,该定义形式应该理解为: dataType *(arrayName[length]); 括号里面说明arrayName是一个数组,包含了length个元素,括号外面说明每个元素的类型为dataType *. 除了每个元素的数据类型不同,指针数组和普通数组在其他方面都是一样的,下面是一个简单的例子: #include <stdi

C语言 结构体数组详解及示例代码

所谓结构体数组,是指数组中的每个元素都是一个结构体.在实际应用中,结构体数组常被用来表示一个拥有相同数据结构的群体,比如一个班的学生.一个车间的职工等. 定义结构体数组和定义结构体变量的方式类似,请看下面的例子: struct stu{ char *name; //姓名 int num; //学号 int age; //年龄 char group; //所在小组 float score; //成绩 }class[5]; 表示一个班级有5个学生. 结构体数组在定义的同时也可以初始化,例如: str

C语言 存储类详解及示例代码

C 存储类 存储类定义 C 程序中变量/函数的范围(可见性)和生命周期.这些说明符放置在它们所修饰的类型之前.下面列出 C 程序中可用的存储类: auto register static extern auto 存储类 auto 存储类是所有局部变量默认的存储类. { int mount; auto int month; } 上面的实例定义了两个带有相同存储类的变量,auto 只能用在函数内,即 auto 只能修饰局部变量. register 存储类 register 存储类用于定义存储在寄存器

Java 数组详解及示例代码

下面是stackoverflow中关于数组方法的相关问题中,获得最多票数的12个数组操作方法. 1.  声明一个数组 String[] aArray = new String[5]; String[] bArray = {"a","b","c", "d", "e"}; String[] cArray = new String[]{"a","b","c&quo

C语言 位运算详解及示例代码

所谓位运算,就是对一个比特(Bit)位进行操作.在<二进制思想以及数据的存储>一节中讲到,比特(Bit)是一个电子元器件,8个比特构成一个字节(Byte),它已经是粒度最小的可操作单元了. C语言提供了六种位运算符: 运算符 & | ^ ~ << >> 说明 按位与 按位或 按位异或 取反 左移 右移 按位与运算(&) 一个比特(Bit)位只有 0 和 1 两个取值,只有参与&运算的两个位都为 1 时,结果才为 1,否则为 0.例如1&1

AngularJs bootstrap详解及示例代码

AngularJs学习笔记系列第一篇,希望我可以坚持写下去.本文内容主要来自 http://docs.angularjs.org/guide/ 文档的内容,但也加入些许自己的理解与尝试结果. 一.总括 本文用于解释Angular初始化的过程,以及如何在你有需要的时候对Angular进行手工初始化. 二.Angular <script> 标签 本例用于展示如何通过推荐的路径整合Angular,实现自动初始化. <!doctype html> <html xmlns:ng=&qu

C语言 字符串指针详解及示例代码

C语言中没有特定的字符串类型,我们通常是将字符串放在一个字符数组中,这在<C语言字符数组和字符串>中已经进行了详细讲解,这里不妨再来演示一下: #include <stdio.h> int main(){ char str[] = "http://c.biancheng.net"; int len = strlen(str), i; //直接输出字符串 printf("%s\n", str); //每次输出一个字符 for(i=0; i<

C语言 文件的打开与关闭详解及示例代码

在C语言中,文件操作都是由库函数来完成的,这节介绍文件的打开和关闭. 文件的打开(fopen函数) fopen() 函数用来打开一个文件,它的原型为: FILE *fopen(char *filename, char *mode); filename为文件名(包括文件路径),mode为打开方式,它们都是字符串.fopen() 会获取文件信息,包括文件名.文件状态.当前读写位置等,并将这些信息保存到一个FILE类型的结构体变量中,然后将该变量的地址返回. FILE是在stdio.h头文件中定义的一

Java 中的注解详解及示例代码

在Java中,注解(Annotation)引入始于Java5,用来描述Java代码的元信息,通常情况下注解不会直接影响代码的执行,尽管有些注解可以用来做到影响代码执行. 注解可以做什么 Java中的注解通常扮演以下角色 编译器指令 构建时指令 运行时指令 其中 Java内置了三种编译器指令,本文后面部分会重点介绍 Java注解可以应用在构建时,即当你构建你的项目时.构建过程包括生成源码,编译源码,生成xml文件,打包编译的源码和文件到JAR包等.软件的构建通常使用诸如Apache Ant和Mav

Android 事件分发详解及示例代码

事件分发是Android中非常重要的机制,是用户与界面交互的基础.这篇文章将通过示例打印出的Log,绘制出事件分发的流程图,让大家更容易的去理解Android的事件分发机制. 一.必要的基础知识 1.相关方法 Android中与事件分发相关的方法主要包括dispatchTouchEvent.onInterceptTouchEvent.onTouchEvent三个方法,而事件分发一般会经过三种容器,分别为Activity.ViewGroup.View.下表对这三种容器分别拥有的事件分发相关方法进行