找出数组中任一重复的数_C++

本文主要是介绍找出数组中任一重复的数_C++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数组中任一重复的数

题目

一个长度为n的数组，数组中的值属于0~(n-1)范围内。现已知该数组中一定有重复的数字，请找出任意一个重复的数字。

思路

如果该数组中没有重复的数字，那么下标和下标对应的值就相等了，即是array[i] == i。利用好这点，寻求解题方法。

• 方法一：(1) 将数组从小到大排序。(2) 遍历判断 array[i] 和 i 之间的关系，不相等，即array[i]重复了。
• 方法二：判断 array[i] 和 i 是否相等。(1) 相等：i++，即判断下一个。(2) 不相等：判断array[i] 和array[array[i]]是否相等。相等即重复了，直接return；不相等，将 array[i] 和array[array[i]]交换。然后又从 i 重新执行思路二的判断。

• 算法选择：方法二
• 方法二为何优于方法一？
  答：方法二循环的主要是为了：将下标 i 相等的值，放到数组下标为 i 的位置。这个过程循环次数小于方法一中的(1)步骤，并且循环过程就判断了是否重复，减少了方法一的(2)步骤。时间复杂度远小于方法一。

代码

#include <stdio.h>
#include <iostream>using namespace std;int duplication = 0;bool testfunc(int num[], int length)
{int i = 0;if((length <= 0) && (num == NULL))return false;for(int i = 0; i < length; i++){if((num[i] < 0) && (num[i] > (length - 1)))return false;    }while(i < length){if(num[i] == i)i++;else{if(num[i] == num[num[i]]){duplication = num[i];return true;    }elseswap(num[i], num[num[i]]);}}return false;
}int main(int argc, char *argv[])
{int length = 8;int num[8] = {2, 7, 2, 3, 4, 5, 1, 5};testfunc(num, length);printf("duplication is : %d\n", duplication);return 0;
}

这篇关于找出数组中任一重复的数_C++的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---