????????數(shù)組是最簡單的數(shù)據(jù)結(jié)構(gòu)曙搬，占據(jù)連續(xù)內(nèi)存并且按順序存儲摔吏。
以下是與數(shù)組有關(guān)的算法題目。
（1）查詢數(shù)組中重復數(shù)字
????????????算法思路：（1）利用hash表纵装，沒有便放進去征讲，有就返回（Java中HashMap存數(shù)字都是對象，判斷數(shù)字是否唯一變?yōu)閷ο笫欠裎ㄒ唬?128-127好說橡娄，其他不好說）诗箍。（2）借助基數(shù)排序思想，創(chuàng)建一個輔助數(shù)組（空間可能會很大）（3）i位置上j和j位置上元素互換瀑踢，若j等于j位置上元素扳还，說明重復（萬一j的大小超出了矩數(shù)組大小則JJ）。（4）先排序橱夭，然后前后指針來實現(xiàn)氨距，若A[i]==A[j] j++;若A[i]!=A[j] i = j;j++;
（2）二維數(shù)組的查找
? ? ? ? ? ? 算法思路：行、列有序棘劣，從小到大俏让，則從右上角開始逼近，縮小搜索范圍。
（3）把數(shù)組中的元素循環(huán)右移k位如12345678右移兩位78123456
? ? ? ? ? ? 算法思路：3次翻轉(zhuǎn)首昔。把123456翻轉(zhuǎn)65432178寡喝；把78翻轉(zhuǎn)65432187；整體翻轉(zhuǎn)78123456勒奇。
（4）字符數(shù)組中所有元素的排列
? ? ? ? ? ? 算法思路：利用遞歸预鬓，第一個字符一共有n種選擇，剩下的變成一個n-1規(guī)模的遞歸問題赊颠。而第一個字符的n種選擇格二，都是字符串里面的。因此可以使用第一個字符與剩下的位置上進行交換竣蹦，得到n種情況顶猜，然后遞歸處理n-1的規(guī)模，只是處理完之后需要在換回來痘括，變成原來字符的樣子长窄。
? ? ? ? ? ? 代碼見：https://github.com/yuanfuqiang456/LeetCode/blob/master/src/Array/Permutation.java
（5）字符數(shù)組中所有元素的組合
? ? ? ? ? ? 算法思路：(1)通過二進制數(shù)字用01表示某個元素是否存在來實現(xiàn)，組合是沒有順序要求的（2）假設(shè)我們想在長度為n的字符串中求m個字符的組合纲菌。我們先從頭掃描字符串的第一個字符挠日。針對第一個字符，我們有兩種選擇：一是把這個字符放到組合中去翰舌，接下來我們需要在剩下的n-1個字符中選取m-1個字符肆资；二是不把這個字符放到組合中去，接下來我們需要在剩下的n-1個字符中選擇m個字符灶芝。這兩種選擇都很容易用遞歸實現(xiàn)。
? ? ? ? ? ? 代碼見：https://github.com/yuanfuqiang456/LeetCode/blob/master/src/Array/Combine.java
（6）判斷數(shù)組中的值是否連續(xù)
? ? ? ? ? ? 算法思路：數(shù)組中的0可以代替任何元素唉韭，如果沒有0夜涕，則說明最大減去最小為數(shù)組大小属愤；如果有0女器，則小于數(shù)組大小。例如：8 7 6 0 5 住诸。
（7）尋找最小k個數(shù)
? ? ? ? ? ? 算法思路：方法一：先對這個序列從小到大排序驾胆，然后輸出前面的最小的k個數(shù)；方法二：是維護容量為k的最大堆贱呐；方法三：快排思想丧诺。Partation，線性時間復雜度算法奄薇。
（8）和為定值的兩個數(shù)
? ? ? ? ? ? 算法思路：1驳阎、二分（若無序，先排序后二分），時間復雜度總為O(N log N)呵晚，空間復雜度為O（1）；2、掃描一遍X-S[i] 映射到一個數(shù)組或構(gòu)造hash表责循，時間復雜度為O(N)歌粥，空間復雜度為O(N)；3金矛、兩個指針兩端掃描（若無序芯急，先排序后掃描），時間復雜度最后為：有序O(N)绷柒，無序O(Nlog N + N)=O(N log N)志于，空間復雜度都為O(1)。
（9）和為定值的多個數(shù)
? ? ? ? ? ? 算法思路：如果取第n個數(shù)废睦，那么問題就轉(zhuǎn)化為“取前n-1個數(shù)使得它們的和為sum-n”伺绽，對應(yīng)的代碼語句就是sumOfkNumber(sum - n, n - 1)；如果不取第n個數(shù)嗜湃，那么問題就轉(zhuǎn)化為“取前n-1個數(shù)使得他們的和為sum”奈应，對應(yīng)的代碼語句為sumOfkNumber(sum, n - 1)。通過遞歸解法求出购披。
? ? ? ? ? ? 代碼見https://github.com/yuanfuqiang456/LeetCode/blob/master/src/Array/KSum.java
（10）奇偶排序
? ??????????輸入一個整數(shù)數(shù)組杖挣，調(diào)整數(shù)組中數(shù)字的順序，使得所有奇數(shù)位于數(shù)組的前半部分刚陡，所有偶數(shù)位于數(shù)組的后半部分惩妇。要求時間復雜度為O(n)。
????????????方法1: 借鑒partition的實現(xiàn)一筐乳，我們可以考慮維護兩個指針歌殃，一個指針指向數(shù)組的第一個數(shù)字，我們稱之為頭指針蝙云，向右移動氓皱；一個指針指向最后一個數(shù)字，稱之為尾指針勃刨，向左移動波材。這樣，兩個指針分別從數(shù)組的頭部和尾部向數(shù)組的中間移動身隐，如果第一個指針指向的數(shù)字是偶數(shù)而第二個指針指向的數(shù)字是奇數(shù)廷区，我們就交換這兩個數(shù)字。
????????????方法2:我們也可以維護兩個指針i和j贾铝，一個指針指向數(shù)組的第一個數(shù)的前一個位置躲因，我們稱之為后指針i早敬，向右移動；一個指針指向數(shù)組第一個數(shù)大脉，稱之為前指針j搞监，也向右移動，且前指針j先向右移動镰矿。如果前指針j指向的數(shù)字是奇數(shù)琐驴，則令i指針向右移動一位，然后交換i和j指針所各自指向的數(shù)字
（11）荷蘭國旗
? ??????????現(xiàn)有n個紅白藍三種不同顏色的小球秤标，亂序排列在一起绝淡，請通過兩兩交換任意兩個球，使得從左至右苍姜，依次是一些紅球牢酵、一些白球、一些藍球衙猪。
? ? ? ? ? ? 算法思路：這個問題類似快排中partition過程馍乙，只是需要用到三個指針：一個前指針begin，一個中指針current垫释，一個后指針end丝格，current指針遍歷整個數(shù)組序列，當
????????????current指針所指元素為0時棵譬，與begin指針所指的元素交換显蝌，而后current++，begin++ 订咸；
????????????current指針所指元素為1時曼尊，不做任何交換（即球不動），而后current++ 脏嚷；
????????????current指針所指元素為2時涩禀，與end指針所指的元素交換，而后然眼，current指針不動，end--
（12）完美洗牌算法
? ??????????有個長度為2n的數(shù)組{a1,a2,a3,...,an,b1,b2,b3,...,bn}葵腹，希望排序后{a1,b1,a2,b2,....,an,bn}高每，請考慮有無時間復雜度o(n)，空間復雜度0(1)的解法践宴。
? ? ? ? ? ? 算法思路：方法1:蠻力B中的數(shù)步步前移鲸匿；或者從中間開始兩兩交換；方法2: 前n個元素中阻肩，第i個元素去了第（2 * i）的位置带欢。后n個元素运授，第i個元素去了第 (2 (i - n) ) - 1 = 2 i - (2 n + 1) = (2 i) % (2 * n + 1) 個位置。
（13）不使用除法進行數(shù)組運算
? ? ? ? ? ? 常見的算法面試題：兩個數(shù)組a[N]乔煞，b[N]吁朦，其中A[N]的各個元素值已知，現(xiàn)給b[i]賦值渡贾，b[i]
= a[0]a[1]a[2]...*a[N-1]/a[i]逗宜；要求解b[i]，但是：
????????????1.不準用除法運算? ??????
????????????2.除了循環(huán)計數(shù)值空骚，a[N],b[N]外纺讲，不準再用其他任何變量（包括局部變量，全局變量等）
????????????3.滿足時間復雜度O(n)囤屹，空間復雜度O(1)熬甚。
????????????算法思路：題目要求b[i] = a[0]a[1]a[2]...a[N-1]/a[i] ，相當于求：a[0]a[1]a[2]a[3]...a[i-1]a[i+1]..a[N-1]肋坚，等價于除掉當前元素a[i]乡括，其他所有元素(a[i]左邊部分，和a[i]右邊部分)的積冲簿。
代碼見https://github.com/yuanfuqiang456/LeetCode/blob/master/src/Array/CalculateWithoutMultiplication.java
（14）數(shù)組中唯一重復元素
????????1-1000放在含有1001個元素的數(shù)組中粟判，只有唯一的一個元素值重復，其它均只出現(xiàn)一次峦剔。每個數(shù)組元素只能訪問一次档礁，設(shè)計一個算法，將它找出來吝沫；不用輔助存儲空間呻澜，能否設(shè)計一個算法實現(xiàn)？
????????算法思路：做加法求和惨险。
（15）找出唯一出現(xiàn)的數(shù)
????????一個數(shù)組里羹幸，數(shù)都是兩兩出現(xiàn)的，但是有三個數(shù)是唯一出現(xiàn)的辫愉，找出這三個數(shù)栅受。
????????算法思路：相同數(shù)做異或運算結(jié)果為0，多次異或運算即可求出恭朗。
（16）找出反序的個數(shù)
????????給定一整型數(shù)組屏镊，若數(shù)組中某個下標值大的元素值小于某個下標值比它小的元素值，稱這是一個反序痰腮。即：數(shù)組a[]; 對于i < j 且 a[i] > a[j],則稱這是一個反序而芥。給定一個數(shù)組，要求寫一個函數(shù)膀值，計算出這個數(shù)組里所有反序的個數(shù)棍丐。
? ? ? ? 算法思想：歸并算法的思路误辑。歸并中需要調(diào)整的次數(shù)即反序的個數(shù)。
（17）兩個數(shù)組元素求和歌逢，最小k個數(shù)
????????有兩個序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升序排列巾钉，對于1<=i,j<=k，求k個最小的（ai+bj）趋翻，要求算法盡量高效睛琳。
? ? ? ? 算法思路：可借助最小堆來解決，由于a1+b1肯定是最小的和踏烙，首先把a1+b1的結(jié)果放大最小堆里师骗，此時堆中只有一個元素，自然滿足最小堆條件讨惩，然后開始出堆的操作辟癌，從堆里面取出根節(jié)點（也就是最小的值），假如此時堆頂元素為ai+bi,則需要像最小堆中壓入a(i+1)+bj的和與ai+b(j+1)的和荐捻，當然黍少，要保證下標不越界，如果下標越界了則忽略处面，另外要保證已經(jīng)壓入過堆中的組合（即使已經(jīng)從堆中被取出了的）不再被壓入堆中厂置。不斷地進行出堆、入堆的操作魂角，重復k次昵济，就得到了k個最小的組合值。
（18）螺旋矩陣
? ??????螺旋狀打印矩陣
（19）一個整數(shù)數(shù)組野揪，長度為n访忿，將其分為m份，使各份的和相等斯稳，求m的最大值海铆。
? ??????比如{3，2挣惰，4卧斟，3，6} 可以分成
????????{3憎茂，2珍语，4，3唇辨，6} m=1;
????????{3,6}{2,4,3} m=2
????????{3,3}{2,4}{6} m=3
????????所以m的最大值為3。????
? ? ????算法思路：從1-N分別劃分能耻，找和為sum/N的數(shù)赏枚；
(20)輸入一個正數(shù)n亡驰，輸出所有和為n連續(xù)正數(shù)序列。
????????例如輸入15饿幅，由于1+2+3+4+5=4+5+6=7+8=15凡辱，所以輸出3個連續(xù)序列1-5、4-6和7-8栗恩。
? ? ? ? 算法思路：和為定值的N個數(shù)的多個K值的版本透乾，且數(shù)字順序要一致。若為奇數(shù)個磕秤，則中間數(shù)字為Sum/N;若為偶數(shù)個乳乌，則sum/n必定余1；通過這種方式市咆，可以求出中間數(shù)字汉操。
（21）找出數(shù)組中兩個只出現(xiàn)一次的數(shù)字
? ??????題目：一個整型數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次蒙兰。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字磷瘤。要求時間復雜度是O(n)，空間復雜度是O(1)搜变。
? ? ? ? 算法思路：異或操作采缚。
（22）把數(shù)組排成最小的數(shù)
? ??????輸入一個正整數(shù)數(shù)組，將它們連接起來排成一個數(shù)挠他，輸出能排出的所有數(shù)字中最小的一個扳抽。例如輸入數(shù)組{32,321}，則輸出這兩個能排成的最小數(shù)字32132绩社。
? ? ? ? 算法思路：字典序排序摔蓝，從前往后合并，如A,B比較AB與BA的大小愉耙，選最小的贮尉，然后逐步縮小數(shù)組長度。
（23）旋轉(zhuǎn)數(shù)組的最小元素
? ??????把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾朴沿，我們稱之為數(shù)組的旋轉(zhuǎn)猜谚。輸入一個排好序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素赌渣。例如數(shù)組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個旋轉(zhuǎn)魏铅，該數(shù)組的最小值為1。
? ? ? ? 算法思路：從頭到尾遍歷數(shù)組一次坚芜，就能找出最小的元素览芳，時間復雜度顯然是O(N)。但這個思路沒有利用輸入數(shù)組的特性鸿竖〔拙梗可以2分查找铸敏，比較找到的元素與首位和末尾的元素，判斷當前元素在哪個遞增序列上悟泵。
（24）請把一個整形數(shù)組中重復的數(shù)字去掉
????????例如：1, 2, 0, 2, -1, 999, 3, 999, 88? ?杈笔；處理后應(yīng)該是：1, 2， 0糕非， -1蒙具， 999， 3朽肥，88
? ? ? ? 算法思路：位圖禁筏，hashtable.
（25）一個數(shù)組[1,2,3,4,6,8,9,4,8,11,18,19,100] 前半部分是是一個遞增數(shù)組，后面一個還是遞增數(shù)組鞠呈，但整個數(shù)組不是遞增數(shù)組融师，那么怎么最快的找出其中一個數(shù)？
? ? ? ? 算法思路：方法一：首先對前一半遞增直接查找蚁吝，找到即退出旱爆，后一半二分查找；方法二：找到零界點窘茁。分兩個部分二分查找怀伦。臨界點可2分查找，比較左右來判斷山林。
（26）數(shù)組al[0,mid-1] 和al[mid,num-1]房待，都分別有序。將其merge成有序數(shù)組al[0,num-1]驼抹，要求空間復雜度O(1)桑孩。
? ? ? ? 算法思路：從中間開始兩兩互換，互換范圍從2-4-6依次擴大框冀。
（27）一個數(shù)組的值先從小到大遞增后從大到小遞減流椒，找出最大的值
? ? ? ? 算法思路：二分查找，找到后和左右比較
（28）兩個無序數(shù)組分別叫A和B明也，長度分別是m和n宣虾，求中位數(shù)，要求時間復雜度O(log（m+n）)温数，空間復雜度O(1)
? ? ? ? 算法思路：首先先排序绣硝，分別求A和B的中位數(shù)，然后比較之撑刺，根據(jù)比較選擇不同的數(shù)組區(qū)域繼續(xù)進行篩選鹉胖。假設(shè)兩個數(shù)組為:Orda_1,Orda_2。先對比這個數(shù)組的中間數(shù)的大小，假設(shè)Orda_1的中間數(shù)為a_1,Orda_2的中間數(shù)為a_2甫菠，如果a_1 >= a_2败许，那么兩個數(shù)組的中間數(shù)肯定在Orda_1數(shù)組前半段和Orda_2數(shù)組后半段中，接著再把Orda_1前半段和Orda_2后半段當做新的兩個有序數(shù)組淑蔚，重復前面的步驟，直至遞歸結(jié)束愕撰。?
（29）約瑟夫環(huán)
? ??????n個數(shù)字（0,1,…,n-1）形成一個圓圈刹衫，從數(shù)字0開始，每次從這個圓圈中刪除第m個數(shù)字（第一個為當前數(shù)字本身搞挣，第二個為當前數(shù)字的下一個數(shù)字）带迟。當一個數(shù)字刪除后，從被刪除數(shù)字的下一個繼續(xù)刪除第m個數(shù)字囱桨。求出在這個圓圈中剩下的最后一個數(shù)字仓犬。
? ? ? ? 算法思路：每殺掉一個人，下一個人成為頭舍肠，相當于把數(shù)組向前移動M位搀继。若已知N-1個人時，勝利者的下標位置位f(N?1,M)翠语，則N個人的時候叽躯，就是往后移動M為，(因為有可能數(shù)組越界肌括，超過的部分會被接到頭上点骑，所以還要模N)，即f(N,M)=(f(N?1,M)+M)%n
????????遞推公式：?
????????????????????f(N,M)=(f(N?1,M)+M)%N
????????????????????f(N,M)表示谍夭，N個人報數(shù)黑滴，每報到M時殺掉那個人，最終勝利者的編號
????????????????????f(N?1,M)表示紧索，N-1個人報數(shù)袁辈，每報到M時殺掉那個人，最終勝利者的編號
? ? ? ? 代碼見：https://github.com/yuanfuqiang456/LeetCode/blob/master/src/Array/JosephLink.java
(30)統(tǒng)計在從1到n的正數(shù)中1出現(xiàn)的次數(shù)
????????例如輸入12齐板，從1到12這些整數(shù)中包含1 的數(shù)字有1吵瞻，10，11和12甘磨，1一共出現(xiàn)了5次橡羞。
? ? ? ? 算法思路：設(shè)定整數(shù)點（如1、10济舆、100等等）作為位置點i（對應(yīng)n的個位卿泽、十位、百位等等），分別對每個數(shù)位上有多少包含1的點進行分析签夭。
????????根據(jù)設(shè)定的整數(shù)位置齐邦，對n進行分割，分為兩部分第租，高位n/i措拇，低位n%i
????????當i表示百位，且百位對應(yīng)的數(shù)>=2,如n=31456,i=100慎宾，則a=314,b=56丐吓，此時百位為1的次數(shù)有a/10+1=32（最高兩位0~31），每一次都包含100個連續(xù)的點趟据，即共有(a/10+1)*100個點的百位為1
????????當i表示百位券犁，且百位對應(yīng)的數(shù)為1，如n=31156,i=100汹碱，則a=311,b=56粘衬，此時百位對應(yīng)的就是1，則共有a/10(最高兩位0-30)次是包含100個連續(xù)點咳促，當最高兩位為31（即a=311）稚新，本次只對應(yīng)局部點00~56，共b+1次跪腹，所有點加起來共有（a/10*100）+(b+1)枷莉，這些點百位對應(yīng)為1
????????當i表示百位，且百位對應(yīng)的數(shù)為0,如n=31056,i=100尺迂，則a=310,b=56笤妙，此時百位為1的次數(shù)有a/10=31（最高兩位0~30）
????????綜合以上三種情況，當百位對應(yīng)0或>=2時噪裕，有(a+8)/10次包含所有100個點蹲盘，還有當百位為1(a%10==1)，需要增加局部點b+1
????????之所以補8膳音，是因為當百位為0召衔，則a/10==(a+8)/10，當百位>=2祭陷，補8會產(chǎn)生進位位苍凛，效果等同于(a/10+1)
（31）數(shù)量超過一半的元素
? ? ? ? ? ? 算法思路：排序，中間元素即是兵志。
（32）兩數(shù)組交換差最小
????????有兩個序列a,b醇蝴，大小都為n,序列元素的值是任意整數(shù)，無序想罕。要求：通過交換a,b中的元素悠栓，使[序列a元素的和]與[序列b元素的和]之間的差最小。
????????例如:
????????????var a=[100,99,98,1,2, 3];
????????????var b=[1, 2, 3, 4,5,40]。
? ? ? ? 算法思路：看交換后兩數(shù)組之和與所有數(shù)據(jù)和的1/2比較惭适。是否更加接近
