写在前面
c++的确是需要一直学习一直积累的编程语言！
1、数组初始化列表中的元素个数小于指定的数组长度时，不足的元素补以默认值。
int a[5] = { 0 }; // 全部初始化为０,等价于 int a[5] = {0,0,0,0,0}
int a[5] = {1}; //第一个元素被赋值为1，其他元素被赋值为0，等价于int a[5] = {1,0,0,0,0}
string a[5] = {"have","fun"}; //第一个元素被赋值为“have”，第二个元素被赋值为“fun”，其他元素被赋值为“”，等价于 string a[5] = {"have","fun","","",""}
2、不能对数组赋值，只能对数组元素初始化或赋值。
int a[3];
a = {10,16,8}; //将会报错： error: assigning to an array from an initializer list
3、当数组作为函数的形参进行传递时，数组就自动退化为同类型的指针。
4、当字符数组表示字符时，若使用sizeof函数，需要将“\0”也计算进去。
说sizeof是函数不太准确，因为sizeof可以不加括号()。需要注意的是无论string里放多长的字符串，它的sizeof()都是固定的，字符串所占的空间是从堆中动态分配的，与sizeof()无关。也就是说sizeof(string)和字符串的长度是无关的，在一个系统中所有的sizeof(string)是一个固定值，这个和编译器相关(经测试，在codeblock中sizeof(string)的固定大小是24个字节)，string字符串是存储在堆上，这个属于动态分配的空间，对于别的整形浮点型数据类型则没有这个问题。
题目一：
在一个长度为n的数组中存放的数字都在0~n-1的范围内。数组中某些数字是重复的，但是不知道具体哪些数字重复了，也不知道重复了几次，请找出数组中任意一个重复的数字。比如说输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出的数字为2或者3。
思路一：把数组中的所有元素从小到大排序。以此扫描排序后的数组，很容易就能找出重复的数字了。排序一个长度为n的数组的时间复杂度为O(nlogn)，不需要额外的空间。
//c++实现
#include <iostream>
#include "stdio.h"
#include<cstring>
using namespace std;
int main()
{
int arr[7] = {2,3,1,0,2,5,3};
int length = sizeof(arr)/sizeof(arr[0]);
int temp;
//选择排序
for(int i = 0;i < length-1;i++){
for(int j=i+1;j<length;j++){
if(arr[i]>arr[j]){
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
//找出所有的重复的数字并输出
for(int i = 0;i<length-1;i++){
if(arr[i]==arr[i+1]){
printf("%d ",arr[i]);
}
}
return 0;
}
思路二：额外定义一个哈希表，从头到尾遍历原数组。若元素不在哈希表中则添加并从原数组中移除；若在哈希表中则说明找到了重复的数字。若只需找一个重复的元素可省去在原数组中移除这一步操作，立即结束程序返回结果；若需要找到所有的重复数字，返回最后的原数组即可。此时遍历数组的时间复杂度为O(n),额外申请的数组的空间复杂度O(n)，由此可见，这个方法是以空间换时间！
水平有限，正在重拾c++，就只用Python随便写了下，将就着看吧。
//python实现
def find(arr):
return set([arr[x] for x in range(len(arr)-1) if arr[x] in arr[x+1:]])
print find([2,3,1,0,5,2,3])
思路三：从头到尾扫描数组，当扫描到下标为i的数字m时，判断下标i与下标i所对应的数字m是否相等，若相等继续扫描下一个元素；判断下标为i的数字即m与下标为m的数字即n是否相等，若相等则说明找到了重复的数字，若不相等就把下标为i的数字m与下标为m的数字n交换位置，继续判断新一轮小标为i的数字n是否与下标i相等。。。如此进行下去，直到找到重复的数字为止。
此法我个人认为对于这道特定的题目来说很有效，但是并不是所有数组的元素都是小于其长度的数字，若有数字大小超过其长度程序就会崩溃，所以没有很好地扩展性。
#include <iostream>
#include "stdio.h"
#include<cstring>
using namespace std;
int main()
{
int arr[7] = {2,3,1,0,2,5,3};
int length = sizeof(arr)/sizeof(arr[0]);
int temp;
for(int i=0;i<length;i++){
while(arr[i]!=i){ //如果下标与下标所对应的数字不相等，就一直交换比较。
if(arr[i]!=arr[arr[i]]){ //下标为i的数字即m与下标为m的数字即n不相等，则把下标为i的数字m与下标为m的数字n交换位置
temp = arr[arr[i]];
arr[arr[i]]=arr[i];
arr[i] = temp;
}
else{
printf("%d ",arr[i]);
break;
}
}
}
}
题目二：
在一个长度为n的数组中存放的数字都在1~n的范围内。数组中某些数字是重复的，所以数组中至少存在一个数字是重复的，请找出数组中任意一个重复的数字，但不能修改输入的数组。比如说输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出的数字为2或者3。也就是说在题目一的基础上增加了一个条件：不能修改数组！！！
思路一：由于不能修改原数组，所以很容易想到的是定义一个长度为n+1的数组，从头到尾遍历原来数组中的数字并判断辅助数组中下标为m的位置上的数字是否为0，若不是则把该数字m存放到这个位置上，若不是为0，则找到了重复的数字。
这个方法呢也是对这道特定的题目有效，虽说时间复杂度为O(n),但是也有O(n)的空间复杂度。而且如果换一个存放较大数字但自身长度很小的数组，该方法就失效了。虽说如此还是用c++实现一下。
#include <iostream>
#include "stdio.h"
#include<cstring>
using namespace std;
int main()
{
int arr[7] = {2,3,1,0,2,5,3};
int length = sizeof(arr)/sizeof(arr[0]);
int help[length+1] = {0}; //数组初始化列表中的元素个数小于指定的数组长度时，不足的元素补以默认值。辅助数组的类型为整型，所以自动补0。
for(int i=0;i<length;i++){
if(help[arr[i]]==0){
help[arr[i]] = arr[i];
}
else{
printf("%d ",arr[i]);
}
}
}
思路二：利用二分查找的算法思想，加一个统计区间内数字数目的步骤。把1-n的数字从中间的数字m分为两部分，前面一半为1-m，后面一半为m+1-n。如果1-m的数字的数目超过m，那么这一半的区间里面一定包含重复的数字，否则重复的数字在另一半区间内。继续把重复数字所在的区间一分为二，一样的方法判断、分割，直到找到重复的数字。
#include <iostream>
#include "stdio.h"
#include<cstring>
using namespace std;
int countRange(int* arr,int length,int star,int middle){
if((sizeof(arr)/sizeof(arr[0]))==0){
return 0;
}
int countsOfnumbers = 0;
for(int i=0;i<length;i++){
if(arr[i] >= star && arr[i]<=middle){
countsOfnumbers += 1;
}
return countsOfnumbers;
}
}
int main(){
int arr[] = {2,3,1,0,2,5,3,3};
int length = sizeof(arr)/sizeof(arr[0]);
int star = 1;
int tail = length-1;
while(tail>=star){
int middle = ((tail-star)>>1)+star;
int countsOfnumbers = countRange(arr,length,star,middle);
if(tail==star){
if(countsOfnumbers>1){
printf("%d ",star);
}
else{
break;
}
}
if(countsOfnumbers>(middle-star+1)){
tail = middle;
}
else{
star = middle + 1;
}
}
}
这个思路存在同样的问题就不累赘了，只适合这道题。
