寫(xiě)在前面
c++的確是需要一直學(xué)習(xí)一直積累的編程語(yǔ)言描馅！
1而线、數(shù)組初始化列表中的元素個(gè)數(shù)小于指定的數(shù)組長(zhǎng)度時(shí)，不足的元素補(bǔ)以默認(rèn)值膀篮。
int a[5] = { 0 }; // 全部初始化為０,等價(jià)于 int a[5] = {0,0,0,0,0}
int a[5] = {1}; //第一個(gè)元素被賦值為1，其他元素被賦值為0磅网，等價(jià)于int a[5] = {1,0,0,0,0}
string a[5] = {"have","fun"}; //第一個(gè)元素被賦值為“have”筷屡，第二個(gè)元素被賦值為“fun”，其他元素被賦值為“”毙死，等價(jià)于 string a[5] = {"have","fun","","",""}
2、不能對(duì)數(shù)組賦值确封，只能對(duì)數(shù)組元素初始化或賦值再菊。
int a[3];
a = {10,16,8}; //將會(huì)報(bào)錯(cuò)： error: assigning to an array from an initializer list
3、當(dāng)數(shù)組作為函數(shù)的形參進(jìn)行傳遞時(shí)腥放，數(shù)組就自動(dòng)退化為同類型的指針绿语。
4、當(dāng)字符數(shù)組表示字符時(shí)吕粹，若使用sizeof函數(shù)，需要將“\0”也計(jì)算進(jìn)去聚请。
說(shuō)sizeof是函數(shù)不太準(zhǔn)確，因?yàn)閟izeof可以不加括號(hào)()驶赏。需要注意的是無(wú)論string里放多長(zhǎng)的字符串，它的sizeof()都是固定的盖文，字符串所占的空間是從堆中動(dòng)態(tài)分配的蚯姆，與sizeof()無(wú)關(guān)。也就是說(shuō)sizeof(string)和字符串的長(zhǎng)度是無(wú)關(guān)的疙驾，在一個(gè)系統(tǒng)中所有的sizeof(string)是一個(gè)固定值郭毕，這個(gè)和編譯器相關(guān)(經(jīng)測(cè)試，在codeblock中sizeof(string)的固定大小是24個(gè)字節(jié))铣卡，string字符串是存儲(chǔ)在堆上，這個(gè)屬于動(dòng)態(tài)分配的空間敞峭，對(duì)于別的整形浮點(diǎn)型數(shù)據(jù)類型則沒(méi)有這個(gè)問(wèn)題蝉仇。
題目一：
在一個(gè)長(zhǎng)度為n的數(shù)組中存放的數(shù)字都在0~n-1的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的沉迹，但是不知道具體哪些數(shù)字重復(fù)了害驹，也不知道重復(fù)了幾次，請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字宛官。比如說(shuō)輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}，那么對(duì)應(yīng)的輸出的數(shù)字為2或者3腋么。
思路一：把數(shù)組中的所有元素從小到大排序亥揖。以此掃描排序后的數(shù)組，很容易就能找出重復(fù)的數(shù)字了。排序一個(gè)長(zhǎng)度為n的數(shù)組的時(shí)間復(fù)雜度為O(nlogn)圣贸，不需要額外的空間扳剿。
//c++實(shí)現(xiàn)
#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;
}
}
}
//找出所有的重復(fù)的數(shù)字并輸出
for(int i = 0;i<length-1;i++){
if(arr[i]==arr[i+1]){
printf("%d ",arr[i]);
}
}
return 0;
}
思路二：額外定義一個(gè)哈希表昼激，從頭到尾遍歷原數(shù)組。若元素不在哈希表中則添加并從原數(shù)組中移除瞧掺；若在哈希表中則說(shuō)明找到了重復(fù)的數(shù)字凡傅。若只需找一個(gè)重復(fù)的元素可省去在原數(shù)組中移除這一步操作，立即結(jié)束程序返回結(jié)果哼转；若需要找到所有的重復(fù)數(shù)字槽华，返回最后的原數(shù)組即可。此時(shí)遍歷數(shù)組的時(shí)間復(fù)雜度為O(n),額外申請(qǐng)的數(shù)組的空間復(fù)雜度O(n)猫态，由此可見(jiàn)，這個(gè)方法是以空間換時(shí)間勇凭！
水平有限义辕，正在重拾c++，就只用Python隨便寫(xiě)了下灌砖，將就著看吧。
//python實(shí)現(xiàn)
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])
思路三：從頭到尾掃描數(shù)組柳譬，當(dāng)掃描到下標(biāo)為i的數(shù)字m時(shí)续镇，判斷下標(biāo)i與下標(biāo)i所對(duì)應(yīng)的數(shù)字m是否相等，若相等繼續(xù)掃描下一個(gè)元素制跟；判斷下標(biāo)為i的數(shù)字即m與下標(biāo)為m的數(shù)字即n是否相等，若相等則說(shuō)明找到了重復(fù)的數(shù)字雨膨，若不相等就把下標(biāo)為i的數(shù)字m與下標(biāo)為m的數(shù)字n交換位置聊记，繼續(xù)判斷新一輪小標(biāo)為i的數(shù)字n是否與下標(biāo)i相等撒妈。排监。舆床。如此進(jìn)行下去棋蚌，直到找到重復(fù)的數(shù)字為止。
此法我個(gè)人認(rèn)為對(duì)于這道特定的題目來(lái)說(shuō)很有效谷暮，但是并不是所有數(shù)組的元素都是小于其長(zhǎng)度的數(shù)字盛垦，若有數(shù)字大小超過(guò)其長(zhǎng)度程序就會(huì)崩潰，所以沒(méi)有很好地?cái)U(kuò)展性省撑。
#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){ //如果下標(biāo)與下標(biāo)所對(duì)應(yīng)的數(shù)字不相等俯在，就一直交換比較。
if(arr[i]!=arr[arr[i]]){ //下標(biāo)為i的數(shù)字即m與下標(biāo)為m的數(shù)字即n不相等跷乐，則把下標(biāo)為i的數(shù)字m與下標(biāo)為m的數(shù)字n交換位置
temp = arr[arr[i]];
arr[arr[i]]=arr[i];
arr[i] = temp;
}
else{
printf("%d ",arr[i]);
break;
}
}
}
}
題目二：
在一個(gè)長(zhǎng)度為n的數(shù)組中存放的數(shù)字都在1~n的范圍內(nèi)愕提。數(shù)組中某些數(shù)字是重復(fù)的，所以數(shù)組中至少存在一個(gè)數(shù)字是重復(fù)的浅侨，請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字，但不能修改輸入的數(shù)組鼓黔。比如說(shuō)輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}，那么對(duì)應(yīng)的輸出的數(shù)字為2或者3崔步。也就是說(shuō)在題目一的基礎(chǔ)上增加了一個(gè)條件：不能修改數(shù)組６泄取！列林！
思路一：由于不能修改原數(shù)組，所以很容易想到的是定義一個(gè)長(zhǎng)度為n+1的數(shù)組捏悬，從頭到尾遍歷原來(lái)數(shù)組中的數(shù)字并判斷輔助數(shù)組中下標(biāo)為m的位置上的數(shù)字是否為0润梯，若不是則把該數(shù)字m存放到這個(gè)位置上甥厦，若不是為0，則找到了重復(fù)的數(shù)字舶赔。
這個(gè)方法呢也是對(duì)這道特定的題目有效谦秧，雖說(shuō)時(shí)間復(fù)雜度為O(n),但是也有O(n)的空間復(fù)雜度。而且如果換一個(gè)存放較大數(shù)字但自身長(zhǎng)度很小的數(shù)組疚鲤，該方法就失效了。雖說(shuō)如此還是用c++實(shí)現(xiàn)一下桶略。
#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}; //數(shù)組初始化列表中的元素個(gè)數(shù)小于指定的數(shù)組長(zhǎng)度時(shí)诲宇，不足的元素補(bǔ)以默認(rèn)值。輔助數(shù)組的類型為整型鹅心，所以自動(dòng)補(bǔ)0纺荧。
for(int i=0;i<length;i++){
if(help[arr[i]]==0){
help[arr[i]] = arr[i];
}
else{
printf("%d ",arr[i]);
}
}
}
思路二：利用二分查找的算法思想溯泣，加一個(gè)統(tǒng)計(jì)區(qū)間內(nèi)數(shù)字?jǐn)?shù)目的步驟榕茧。把1-n的數(shù)字從中間的數(shù)字m分為兩部分，前面一半為1-m肢簿，后面一半為m+1-n蜻拨。如果1-m的數(shù)字的數(shù)目超過(guò)m，那么這一半的區(qū)間里面一定包含重復(fù)的數(shù)字缎讼，否則重復(fù)的數(shù)字在另一半?yún)^(qū)間內(nèi)。繼續(xù)把重復(fù)數(shù)字所在的區(qū)間一分為二卧惜，一樣的方法判斷夹纫、分割，直到找到重復(fù)的數(shù)字茅姜。
#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;
}
}
}
這個(gè)思路存在同樣的問(wèn)題就不累贅了月匣，只適合這道題。
