对于一个SIZE大小的数组,元素是[0,SIZE-1]区间内的整数,判断其中是否有重复元素

By | 07月16日
Advertisement

bool IsUnique(int *ver,int const SIZE,int const iBegin=0)

//ver[SIZE]保存的是[ iBegin,iBegin+SIZE-1]区间的值

//注意:该算法会破坏原数组数据

//扩展:对于ver[SIZE]的数组,如果里面保存的数据是[iBegin,iBegin+SIZE-1]

//区间的值且不能重复,上面的程序稍微修改一下就能实现O(N)时间复杂度和O(1)

//空间复杂度的排序

{

int iCount=0;

for (int i=0;iCount<SIZE&&i<SIZE;++i)

{

if (ver[i]==i+iBegin)

{

continue;

}

while (ver[i]!=i+iBegin)

{

if (ver[i]==ver[ver[i]-iBegin])

{

return false;

}

swap(ver[i],ver[ver[i]-iBegin]);

++iCount;

}

++iCount;

}

return true;

}

bool IsUnique(unsigned int *ver,size_t const SIZE)

//ver[SIZE]保存的是[ 0,SIZE-1]区间的值

//注意:该算法不会破坏原数组元素,不过有个限制,就是必须满足:SIZE<2^31-1,

//当然对于long long类型的数组,是SIZE<2^63-1;当然要达到那样大的元素,

//几率不大

{

int iCount=0;

int i=0;

for (;i<SIZE;++i)

{

int iIndex=ver[i]&0X7FFFFFFF;

if ((ver[iIndex]&0X80000000))

{

break;

}

ver[iIndex]|=0X80000000;

}

for (int j=0;j<SIZE;++j)

{

ver[j]&=0X7FFFFFFF;

}

return i==SIZE;

}

版权声明:本文为博主原创文章,未经博主允许不得转载。

Similar Posts:

  • net c#数组问题 声明一个100大小的数组 随机插入1-100之间的数,不能重复

    碰到的一个面试题,写出来大家分享,希望给与指正. void Main() { getRandowArray produceArr=new getRandowArray(); int [] arr=produceArr.produceRandomArray(); for(int i=0;i<arr.Length;++i) { Console.WriteLine(arr[i]); } } class getRandowArray { public getRandowArray() { arr=new

  • 如何判断一个整数数组中是否有重复元素?要求时间复杂度O(n),空间复杂度O(1)

    题目: 写一个函数判断一个int类型的数组是否是有效的. 所谓有效是指:假设数组大小为n,那么这个int数组里的值为0~n-1之间的数,并且每个数只能出现一次,否则就是无效数组. 例如[5,3,1,4,2,0]是有效的,[5,3,5,1,2,0]是无效的,[5,3,6,1,2,0]是无效的. 解法思路一:置换的思想 用一个temp来存储被置换出来的值,例如数组a: 5 3 1 4 2 0 首先,初始化时取第一个数5,将5放在数组的第5号位置,将原来的位置改为-1,5号被置换出来的值放在 temp

  • 已知一个几乎有序的数组,几乎有序是指,如果把数组排好顺序的话,每个元素移动的距离可以不超过k,并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。 给定一个int数组A,同时给定

    已知一个几乎有序的数组,几乎有序是指,如果把数组排好顺序的话,每个元素移动的距离可以不超过k, 并且k相对于数组来说比较小.请选择一个合适的排序算法针对这个数据进行排序给定一个int数组A, 同时给定A的大小n和题意中的k,请返回排序后的数组. 思路:使用空间复杂度为O(nlogn)中的堆排序,因为快速排序是随机选取一个数然后左右分段,归并排序是分成n 个只有一个元素的序列,他们与序列顺序关系不大,所以选用堆排序解决. 1.建立由k可元素的小顶堆,然后取出顶上元素 2.堆顶用没有建堆的下一元素替

  • Java代码实现删除一个有序数组里面的重复元素

    放松了这么多天,终于把博客重新捡起来了,以后保持每天3更,加油加油! 这次实现的算法是删除一个有序数组里面的重复元素 思路:一个数组是有序的,所以算法实现起来相对比较简单,因为只需比较数组相邻的两个数字即可,存在两种情况 1:如果数组里面不存在元素或者只存在一个元素,那么就不需要进行比较,直接返回数组的长度即可: 2:数组长度大于一的话那么就需要比较数组的相邻的两个元素,如果相等 的话那么后一个元素的指针往后移一位,然后前一个元素的指针接着往后移一位,将当前后一个元素指针所指的数字赋给前一个元素

  • 输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素

    /** * * 输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素 * */ public class MinNum { public void findMin(int[] a){ //指向第一个元素的指针 int low = 0; //指向最后一个元素的指针 int high = a.length - 1; if(a[low] < a[high]){ System.out.println(a[low]); return; } //当无法确认中间的数字是位于前面的子数组还是位于后面的子数组

  • 网易游戏笔试题:输入一个数n,返回一个数组,数组中每个元素对应[0,n]每个数的二进制中1的个数

    题目: 输入一个数n(保证输入正数),返回一个数组,数组中每个元素对应[0,n]每个数的二进制中1的个数 如:n=5,返回A=[0,1,1,2,1,2] 给出的函数声明int* BitCountArr(int n,int *sizeArr): #include<iostream> using namespace std; int* BitCountArr1(int n,int *sizeArr)//方法一 { sizeArr = new int[n + 1]; int j = 0; for (

  • 判断一个任意大小的矩阵是否为单位矩阵

    <C和指针>第8章编程练习第4题: 修改前一个问题中的 identity_matrix 函数,它可以对数组进行扩展,从而能够接受任意大小的矩阵参数.函数的第1个参数应该是一个整型指针,你需要第2个参数,用于指定矩阵的大小. 1 /* 2 ** 判断一个矩阵是否为单位矩阵 3 ** 矩阵为任意大小 4 */ 5 6 #include <stdio.h> 7 #define SIZE 4 8 9 /* 10 ** 函数接受任意大小矩阵参数,判断它是否为单位矩阵 11 ** 形参: 12

  • 使struct对象拥有可变大小的数组——(C++深度探索)

    首先摘录<Inside The C++ Object Model>中的一段话: 把单一元素的数组放在一个struct的尾端,于是每个 struct objects 可以拥有可变大小的数组: struct mumble { char pc[1]; }; //获取一个字符串,然后为struct本身和该字符串配置足够的内存 struct mumble *pmumbl = (struct mumble*)malloc(sizeof(struct mumble) + strlen(string) + 1

  • 统计一个数字在排序数组中出现的次数

    题目描述: 统计一个数字在排序数组中出现的次数. 输入: 每个测试案例包括两行: 第一行有1个整数n,表示数组的大小.1<=n <= 10^6. 第二行有n个整数,表示数组元素,每个元素均为int. 第三行有1个整数m,表示接下来有m次查询.1<=m<=10^3. 下面有m行,每行有一个整数k,表示要查询的数. 输出: 对应每个测试案例,有m行输出,每行1整数,表示数组中该数字出现的次数. 样例输入: 81 2 3 3 3 3 4 513 样例输出: 4 解:用二分查找两次,确定要

  • 给定一个2n长的数组将奇数放在偶数前面

    给定一个2n长数组,其中n个奇数和n个偶数,对数组进行排序将奇数放在前半部分,偶数放在后半部分.要求: 不改变原来的奇偶各自的相对顺序 只申请常数的空间 时间复杂度为O(n) 举例:给出1 2 3 4 5 6排序后为 1 3 5 2 4 6 PS:请一定仔细阅读3个条件,去掉其中任意一个都变得简单,并且网上我搜到的答案都是缺少其中某个条件的.因此我怀疑这题是否有解. 看了大家的回答,基本可以分为2种情况: 用链表可以轻易解决这道题,当然如果把数组转成链表因为需要申请2n长度的next数组,所以认

Tags: