經典面試演算法題

Ⅰ 演算法面試

我在《再談「我是怎麼招程序員」》中比較保守地說過，「問難的演算法題並沒有錯，錯的很多面試官只是在膚淺甚至錯誤地理解著面試演算法題的目的。」，今天，我想加強一下這個觀點——我反對純演算法題面試！（注意，我說的是純演算法題）圖片源Wikipedia（點擊圖片查看詞條）我再次引用我以前的一個觀點——能解演算法題並不意味著這個人就有能力就能在工作中解決問題，你可以想想，小學奧數題可能比這些題更難，但並不意味著那些奧數能手就能解決實際問題。好了，讓我們來看一個示例（這個示例是昨天在微博上的一個討論），這個題是——「找出無序數組中第2大的數」，幾乎所有的人都用了O(n)的演算法，我相信對於我們這些應試教育出來的人來說，不用排序用O(n)演算法是很正常的事，連我都不由自主地認為O(n)演算法是這個題的標准答案。我們太習慣於標准答案了，這是我國教育最悲哀的地方。（廣義的洗腦就是讓你的意識依賴於某個標准答案，然後通過給你標准答案讓你不會思考而控制你）功能性需求分析試想，如果我們在實際工作中得到這樣一個題 我們會怎麼做？我一定會分析這個需求，因為我害怕需求未來會改變，今天你叫我找一個第2大的數，明天你找我找一個第4大的數，後天叫我找一個第100大的數，我不搞死了。需求變化是很正常的事。分析完這個需求後，我會很自然地去寫找第K大數的演算法——難度一下子就增大了。很多人會以為找第K大的需求是一種「過早擴展」的思路，不是這樣的，我相信我們在實際編碼中寫過太多這樣的程序了，你一定不會設計出這樣的函數介面 —— Find2ndMaxNum(int* array, int len)，就好像你不會設計出 DestroyBaghdad(); 這樣的介面，而是設計一個DestoryCity( City& ); 的介面，而把Baghdad當成參數傳進去！所以，你應該是聲明一個叫FindKthMaxNum(int* array, int len, int kth)，把2當成參數傳進去。這是最基本的編程方法，用數學的話來說，叫代數！最簡單的需求分析方法就是把需求翻譯成函數名，然後看看是這個介面不是很二？！（註：不要糾結於FindMaxNum()或FindMinNum()，因為這兩個函數名的業務意義很清楚了，不像Find2ndMaxNum()那麼二）非功能性需求分析性能之類的東西從來都是非功能性需求，對於演算法題，我們太喜歡研究演算法題的空間和時間復雜度了。我們希望做到空間和時間雙豐收，這是演算法學術界的風格。所以，習慣於標准答案的我們已經失去思考的能力，只會機械地思考演算法之內的性能，而忽略了演算法之外的性能。如果題目是——「從無序數組中找到第K個最大的數」，那麼，我們一定會去思考用O(n)的線性演算法找出第K個數。事實上，也有線性演算法——STL中可以用nth_element求得類似的第n大的數，其利用快速排序的思想，從數組S中隨機找出一個元素X，把數組分為兩部分Sa和Sb。Sa中的元素大於等於X，Sb中元素小於X。這時有兩種情況：1）Sa中元素的個數小於k，則Sb中的第 k-|Sa|個元素即為第k大數；2） Sa中元素的個數大於等於k，則返回Sa中的第k大數。時間復雜度近似為O(n)。搞學術的nuts們到了這一步一定會歡呼勝利！但是他們哪裡能想得到性能的需求分析也是來源自業務的！我們一說性能，基本上是個人都會問，請求量有多大？如果我們的FindKthMaxNum()的請求量是m次，那麼你的這個每次都要O(n)復雜度的演算法得到的效果就是O(n*m)，這一點，是書獃子式的學院派人永遠想不到的。因為應試教育讓我們不會從實際思考了。工程式的解法根據上面的需求分析，有軟體工程經驗的人的解法通常會這樣：1）把數組排序，從大到小。2）於是你要第k大的數，就直接訪問 array[k]。排序只需要一次，O(n*log(n))，然後，接下來的m次對FindKthMaxNum()的調用全是O(1)的，整體復雜度反而成了線性的。其實，上述的還不是工程式的最好的解法，因為，在業務中，那數組中的數據可能會是會變化的，所以，如果是用數組排序的話，有數據的改動會讓我重新排序，這個太耗性能了，如果實際情況中會有很多的插入或刪除操作，那麼可以考慮使用B+樹。工程式的解法有以下特點：1）很方便擴展，因為數據排好序了，你還可以方便地支持各種需求，如從第k1大到k2大的數據（那些學院派寫出來的代碼在拿到這個需求時又開始撓頭苦想了）2）規整的數據會簡化整體的演算法復雜度，從而整體性能會更好。（公欲善其事，必先利其器）3）代碼變得清晰，易懂，易維護！（學院派的和STL一樣的近似O(n)復雜度的演算法沒人敢動）爭論你可能會和我有以下爭論，如果程序員做這個演算法題用排序的方式，他一定不會像你想那麼多。是的，你說得對。但是我想說，很多時候，我們直覺地思考，恰恰是正確的路。因為「排序」這個思路符合人類大腦處理問題的方式，而使用學院派的方式是反大腦直覺的。反大腦直覺的，通常意味著晦澀難懂，維護成本上升。就是一道面試題，我就是想測試一下你的演算法技能，這也扯太多了。沒問題，不過，我們要清楚我們是在招什麼人？是一個只會寫演算法的人，還是一個會做軟體的人？這個只有你自己最清楚。這個演算法題太容易誘導到學院派的思路了。是的這道「找出第K大的數」，其實可以變換為更為業務一點的題目——「我要和別的商戶競價，我想排在所有競爭對手報價的第K名，請寫一個程序，我輸入K，和一個商品名，系統告訴我應該訂多少價？（商家的所有商品的報價在一數組中）」——業務分析，整體性能，演算法，數據結構，增加需求讓應聘者重構，這一個問題就全考了。你是不是在說演算法不重要，不用學？千萬別這樣理解我，搞得好像如果面試不面，我就可以不學。演算法很重要，演算法題能鍛煉我們的思維，而且也有很多實際用處。我這篇文章不是讓大家不要去學演算法，這是完全錯誤的，我是讓大家帶著業務問題去使用演算法。問你業務問題，一樣會問到演算法題上來。小結看過這上面的分析，我相信你明白我為什麼反對純演算法面試題了。原因就是純演算法的面試題根本不能反應一個程序的綜合素質！那麼，在面試中，我們應該要考量程序員的那些綜合素質呢？我以為有下面這些東西：會不會做需求分析？怎麼理解問題的？解決問題的思路是什麼？想法如何？會不會對基礎的演算法和數據結構靈活運用？另外，我們知道，對於軟體開發來說，在工程上，難是的下面是這些挑戰：軟體的維護成本遠遠大於軟體的開發成本。軟體的質量變得越來越重要，所以，測試工作也變得越來越重要。軟體的需求總是在變的，軟體的需求總是一點一點往上加的。程序中大量的代碼都是在處理一些錯誤的或是不正常的流程。所以，對於編程能力上，我們應該主要考量程序員的如下能力：設計是否滿足對需求的理解，並可以應對可能出現的需求變化。

Ⅱ java演算法面試題：排序都有哪幾種方法

一、冒泡排序
[java] view plain
package sort.bubble;
import java.util.Random;
/**
* 依次比較相鄰的兩個數，將小數放在前面，大數放在後面
* 冒泡排序，具有穩定性
* 時間復雜度為O（n^2）
* 不及堆排序，快速排序O（nlogn，底數為2）
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for(int i = 0 ; i < 10 ; i++){
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的數組為");
for(int i : sort){
System.out.print(i+" ");
}
buddleSort(sort);
System.out.println();
System.out.print("排序後的數組為");
for(int i : sort){
System.out.print(i+" ");
}
}
/**
* 冒泡排序
* @param sort
*/
private static void buddleSort(int[] sort){
for(int i=1;i<sort.length;i++){
for(int j=0;j<sort.length-i;j++){
if(sort[j]>sort[j+1]){
int temp = sort[j+1];
sort[j+1] = sort[j];
sort[j] = temp;
}
}
}
}
}
二、選擇排序
[java] view plain
package sort.select;
import java.util.Random;
/**
* 選擇排序
* 每一趟從待排序的數據元素中選出最小（或最大）的一個元素，
* 順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。
* 選擇排序是不穩定的排序方法。
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0; i < 10; i++) {
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的數組為");
for (int i : sort) {
System.out.print(i + " ");
}
selectSort(sort);
System.out.println();
System.out.print("排序後的數組為");
for (int i : sort) {
System.out.print(i + " ");
}
}
/**
* 選擇排序
* @param sort
*/
private static void selectSort(int[] sort){
for(int i =0;i<sort.length-1;i++){
for(int j = i+1;j<sort.length;j++){
if(sort[j]<sort[i]){
int temp = sort[j];
sort[j] = sort[i];
sort[i] = temp;
}
}
}
}
}
三、快速排序
[java] view plain
package sort.quick;
/**
* 快速排序 通過一趟排序將要排序的數據分割成獨立的兩部分， 其中一部分的所有數據都比另外一部分的所有數據都要小，
* 然後再按此方法對這兩部分數據分別進行快速排序， 整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
* @author liangge
*
*/
public class Main {
public static void main(String[] args) {
int[] sort = { 54, 31, 89, 33, 66, 12, 68, 20 };
System.out.print("排序前的數組為：");
for (int data : sort) {
System.out.print(data + " ");
}
System.out.println();
quickSort(sort, 0, sort.length - 1);
System.out.print("排序後的數組為：");
for (int data : sort) {
System.out.print(data + " ");
}
}
/**
* 快速排序
* @param sort 要排序的數組
* @param start 排序的開始座標
* @param end 排序的結束座標
*/
public static void quickSort(int[] sort, int start, int end) {
// 設置關鍵數據key為要排序數組的第一個元素，
// 即第一趟排序後，key右邊的數全部比key大，key左邊的數全部比key小
int key = sort[start];
// 設置數組左邊的索引，往右移動判斷比key大的數
int i = start;
// 設置數組右邊的索引，往左移動判斷比key小的數
int j = end;
// 如果左邊索引比右邊索引小，則還有數據沒有排序
while (i < j) {
while (sort[j] > key && j > start) {
j--;
}
while (sort[i] < key && i < end) {
i++;
}
if (i < j) {
int temp = sort[i];
sort[i] = sort[j];
sort[j] = temp;
}
}
// 如果左邊索引比右邊索引要大，說明第一次排序完成，將sort[j]與key對換，
// 即保持了key左邊的數比key小，key右邊的數比key大
if (i > j) {
int temp = sort[j];
sort[j] = sort[start];
sort[start] = temp;
}
//遞歸調用
if (j > start && j < end) {
quickSort(sort, start, j - 1);
quickSort(sort, j + 1, end);
}
}
}
[java] view plain
/**
* 快速排序
*
* @param a
* @param low
* @param high
* voidTest
*/
public static void kuaisuSort(int[] a, int low, int high)
{
if (low >= high)
{
return;
}
if ((high - low) == 1)
{
if (a[low] > a[high])
{
swap(a, low, high);
return;
}
}
int key = a[low];
int left = low + 1;
int right = high;
while (left < right)
{
while (left < right && left <= high)// 左邊向右
{
if (a[left] >= key)
{
break;
}
left++;
}
while (right >= left && right > low)
{
if (a[right] <= key)
{
break;
}
right--;
}
if (left < right)
{
swap(a, left, right);
}
}
swap(a, low, right);
kuaisuSort(a, low, right);
kuaisuSort(a, right + 1, high);
}
四、插入排序
[java] view plain
package sort.insert;
/**
* 直接插入排序
* 將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據
* 演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。
*/
import java.util.Random;
public class DirectMain {
public static void main(String[] args) {
Random ran = new Random();
int[] sort = new int[10];
for (int i = 0; i < 10; i++) {
sort[i] = ran.nextInt(50);
}
System.out.print("排序前的數組為");
for (int i : sort) {
System.out.print(i + " ");
}
directInsertSort(sort);
System.out.println();
System.out.print("排序後的數組為");
for (int i : sort) {
System.out.print(i + " ");
}
}
/**
* 直接插入排序
*
* @param sort
*/
private static void directInsertSort(int[] sort) {
for (int i = 1; i < sort.length; i++) {
int index = i - 1;
int temp = sort[i];
while (index >= 0 && sort[index] > temp) {
sort[index + 1] = sort[index];
index--;
}
sort[index + 1] = temp;
}
}
}
順便添加一份，差不多的
[java] view plain
public static void charuSort(int[] a)
{
int len = a.length;
for (int i = 1; i < len; i++)
{
int j;
int temp = a[i];
for (j = i; j > 0; j--)//遍歷i之前的數字
{
//如果之前的數字大於後面的數字，則把大的值賦到後面
if (a[j - 1] > temp)
{
a[j] = a[j - 1];
} else
{
break;
}
}
a[j] = temp;
}
}
把上面整合起來的一份寫法：
[java] view plain
/**
* 插入排序:
*
*/
public class InsertSort {
public void sort(int[] data) {
for (int i = 1; i < data.length; i++) {
for (int j = i; (j > 0) && (data[j] < data[j - 1]); j--) {
swap(data, j, j - 1);
}
}
}
private void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
五、順便貼個二分搜索法
[java] view plain
package search.binary;
public class Main {
public static void main(String[] args) {
int[] sort = {1,2,3,4,5,6,7,8,9,10};
int mask = binarySearch(sort,6);
System.out.println(mask);
}
/**
* 二分搜索法，返回座標，不存在返回-1
* @param sort
* @return
*/
private static int binarySearch(int[] sort,int data){
if(data<sort[0] || data>sort[sort.length-1]){
return -1;
}
int begin = 0;
int end = sort.length;
int mid = (begin+end)/2;
while(begin <= end){
mid = (begin+end)/2;
if(data > sort[mid]){
begin = mid + 1;
}else if(data < sort[mid]){
end = mid - 1;
}else{
return mid;
}
}
return -1;
}
}

Ⅲ 面試中的計算題

算題者自己搞糊塗了，犯了邏輯上的錯誤。其實，根本就不存在少了10美元的問題。錯誤在於，說每個人實際交了90美元，共收3×90＝270美元，這是對的，但不用這270美元去加20美元，而應加退給他們的30美元，正好等於300美元。因為人家交的270美元中，被服務員拿了20美元，這20美元就在270美元裡面，怎麼還能去和270美元相加呢？如果20美元要加，只能與經理那裡的250美元相加，再加退給三人的30美元，總計300美元。這個問題實際上是個數學問題，也是個邏輯問題。

Ⅳ android 面試，演算法題。

final int size = data.length;
for(int i = 0; i< size; i++){
if(data[i] == 0xffffffff)
data[i] = 0x80ffffff;
}

不知道你是不是這個意思。

Ⅳ java面試有哪些演算法

面試-java演算法題：
1.編寫一個程序，輸入n,求n！（用遞歸的方式實現）。
public static long fac(int n){ if(n<=0) return 0; else if(n==1) return 1; else return n*fac(n-1);
} public static void main(String [] args) {
System.out.println(fac(6));
}
2.編寫一個程序，有1，2,3,4個數字，能組成多少個互不相同且無重復數字的三位數？都是多少？
public static void main(String [] args) { int i, j, k; int m=0; for(i=1;i<=4;i++) for(j=1;j<=4;j++) for(k=1;k<=4;k++){ if(i!=j&&k!=j&&i!=k){
System.out.println(""+i+j+k);
m++;
}
}
System.out.println("能組成："+m+"個");
}
3.編寫一個程序，將text1.txt文件中的單詞與text2.txt文件中的單詞交替合並到text3.txt文件中。text1.txt文件中的單詞用回車符分隔，text2.txt文件中用回車或空格進行分隔。
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;

public class text{
public static void main(String[] args) throws Exception{
String[] a = getArrayByFile("text1.txt",new char[]{'\n'});
String[] b = getArrayByFile("text2.txt",new char[]{'\n',' '});
FileWriter c = new FileWriter("text3.txt");
int aIndex=0; int bIndex=0;

while(aIndex<a.length){
c.write(a[aIndex++] + "\n");
if(bIndex<b.length)
c.write(b[bIndex++] + "\n");
}

while(bIndex<b.length){
c.write(b[bIndex++] + "\n");
}
c.close();
}

public static String[] getArrayByFile(String filename,char[] seperators) throws Exception{
File f = new File(filename);
FileReader reader = new FileReader(f);
char[] buf = new char[(int)f.length()];
int len = reader.read(buf);
String results = new String(buf,0,len);
String regex = null;
if(seperators.length >1 ){
regex = "" + seperators[0] + "|" + seperators[1];
}else{
regex = "" + seperators[0];
}
return results.split(regex);
}

}
4.639172每個位數上的數字都是不同的，且平方後所得數字的所有位數都不會出現組成它自身的數字。（639172*639172=408540845584），類似於639172這樣的6位數還有幾個？分別是什麼？
這題採用的HashMap結構判斷有無重復，也可以採用下題的數組判斷。
public void selectNum(){
for(long n = 100000; n <= 999999;n++){
if(isSelfRepeat(n)) //有相同的數字，則跳過
continue;
else if(isPingFangRepeat(n*n,n)){ //該數的平方中是否有與該數相同的數字
continue;
} else{ //符合條件，則列印 System.out.println(n);
}
}
} public boolean isSelfRepeat(long n){
HashMap<Long,String> m=new HashMap<Long,String>(); //存儲的時候判斷有無重復值
while(n!=0){ if(m.containsKey(n%10)){ return true;
} else{
m.put(n%10,"1");
}
n=n/10;
} return false;
} public boolean isPingFangRepeat(long pingfang,long n){
HashMap<Long,String> m=new HashMap<Long,String>(); while(n!=0){
m.put(n%10,"1");
n=n/10;
} while(pingfang!=0){ if(m.containsKey(pingfang%10)){ return true;
}
pingfang=pingfang/10;
} return false;
} public static void main(String args[]){ new test().selectNum();
}
5.比如，968548+968545=321732732它的答案里沒有前面兩個數里的數字，有多少這樣的6位數。
public void selectNum(){
for(int n = 10; n <= 99;n++){
for(int m = 10; m <= 99;m++){ if(isRepeat(n,m)){ continue;
} else{
System.out.println("組合是"+n+","+m);
}
}
}
} public boolean isRepeat(int n,int m){ int[] a={0,0,0,0,0,0,0,0,0,0}; int s=n+m; while(n!=0){
a[n%10]=1;
n=n/10;
} while(m!=0){
a[m%10]=1;
m=m/10;
} while(s!=0){ if(a[s%10]==1){ return true;
}
s=s/10;
} return false;
} public static void main(String args[]){ new test().selectNum();
}
6.給定String,求此字元串的單詞數量。字元串不包括標點，大寫字母。例如 String str="hello world hello hi";單詞數量為3，分別是：hello world hi。
public static void main(String [] args) { int count = 0;
String str="hello world hello hi";
String newStr="";
HashMap<String,String> m=new HashMap<String,String>();
String [] a=str.split(" "); for (int i=0;i<a.length;i++){ if(!m.containsKey(a[i])){
m.put(a[i],"1");
count++;
newStr=newStr+" "+a[i];
}
}
System.out.println("這段短文單詞的個數是："+count+","+newStr);
}
7.寫出程序運行結果。
public class Test1 { private static void test(int[]arr) { for (int i = 0; i < arr.length; i++) { try { if (arr[i] % 2 == 0) { throw new NullPointerException();
} else {
System.out.print(i);
}
} catch (Exception e) {
System.out.print("a ");
} finally {
System.out.print("b ");
}
}
}
public static void main(String[]args) { try {
test(new int[] {0, 1, 2, 3, 4, 5});
} catch (Exception e) {
System.out.print("c ");
}
}

}
運行結果：a b 1b a b 3b a b 5b
public class Test1 { private static void test(int[]arr) { for (int i = 0; i < arr.length; i++) { try { if (arr[i] % 2 == 0) { throw new NullPointerException();
} else {
System.out.print(i);
}
}
finally {
System.out.print("b ");
}
}
}
public static void main(String[]args) { try {
test(new int[] {0, 1, 2, 3, 4, 5});
} catch (Exception e) {
System.out.print("c ");
}
}

}
運行結果：b c
8.單詞數
統計一篇文章里不同單詞的總數。
Input
有多組數據，每組一行，每組就是一篇小文章。每篇小文章都是由小寫字母和空格組成，沒有標點符號，遇到#時表示輸入結束。
Output
每組值輸出一個整數，其單獨成行，該整數代表一篇文章里不同單詞的總數。
Sample Input
you are my friend
#
Sample Output
4
public static void main(String [] args) {
List<Integer> countList=new ArrayList<Integer>(); int count;
HashMap<String,String> m;
String str; //讀取鍵盤輸入的一行（以回車換行為結束輸入） String[] a;

Scanner in=new Scanner(System.in);
while( !(str=in.nextLine()).equals("#") ){
a=str.split(" ");
m=new HashMap<String,String>();
count = 0; for (int i=0;i<a.length;i++){ if(!m.containsKey(a[i]) && (!a[i].equals(""))){
m.put(a[i],"1");
count++;
}
}
countList.add(count);
}s for(int c:countList)
System.out.println(c);
}

Ⅵ 大公司筆試面試有哪些經典演算法題目

1、二維數組中的查找

具體例題：如果一個數字序列逆置之後跟原序列是一樣的就稱這樣的數字序列為迴文序列。例如：{1, 2, 1}, {15, 78, 78, 15} , {112} 是迴文序列, {1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是迴文序列。現在給出一個數字序列，允許使用一種轉換操作：選擇任意兩個相鄰的數，然後從序列移除這兩個數，並用這兩個數字的和插入到這兩個數之前的位置(只插入一個和)。現在對於所給序列要求出最少需要多少次操作可以將其變成迴文序列？

Ⅶ 一道經典的面試題：如何從N個數中選出最大（小）的n個數

這個問題我前前後後考慮了有快一年了，也和不少人討論過。據我得到的消息，Google和微軟都面過這道題。這道題可能很多人都聽說過，或者知道答案（所謂的堆），不過我想把我的答案寫出來。我的分析也許存有漏洞，以交流為目的。但這是一個滿復雜的問題，蠻有趣的。看完本文，也許會啟發你一些沒有想過的解決方案（我一直認為堆也許不是最高效的演算法）。在本文中，將會一直以尋找n個最大的數為分析例子，以便統一。註：本文寫得會比較細節一些，以便於絕大多數人都能看懂，別嫌我羅嗦:) 我很不確定多少人有耐心看完本文！ Naive 方法： 首先，我們假設n和N都是內存可容納的，也就是說N個數可以一次load到內存里存放在數組里（如果非要存在鏈表估計又是另一個challenging的問題了）。從最簡單的情況開始，如果n=1，那麼沒有任何疑惑，必須要進行N-1次的比較才能得到最大的那個數，直接遍歷N個數就可以了。如果n=2呢？當然，可以直接遍歷2遍N數組，第一遍得到最大數max1，但是在遍歷第二遍求第二大數max2的時候，每次都要判斷從N所取的元素的下標不等於max1的下標，這樣會大大增加比較次數。對此有一個解決辦法，可以以max1為分割點將N數組分成前後兩部分，然後分別遍歷這兩部分得到兩個最大數，然後二者取一得到max2。 也可以遍歷一遍就解決此問題，首先維護兩個元素max1，max2（max1=max2），取到N中的一個數以後，先和max1比，如果比max1大（則肯定比max2大），直接替換max1，否則再和max2比較確定是否替換max2。採用類似的方法，對於n=2，3，4一樣可以處理。這樣的演算法時間復雜度為O（nN）。當n越來越大的時候（不可能超過N/2，否則可以變成是找N-n個最小的數的對偶問題），這個演算法的效率會越來越差。但是在n比較小的時候（具體多小不好說），這個演算法由於簡單，不存在遞歸調用等系統損耗，實際效率應該很不錯. 堆：當n較大的時候採用什麼演算法呢？首先我們分析上面的演算法，當從N中取出一個新的數m的時候，它需要依次和max1，max2，max3max n比較，一直找到一個比m小的max x，就用m來替換max x，平均比較次數是n/2。可不可以用更少的比較次數來實現替換呢？最直觀的方法是，也就是網上文章比較推崇的堆。堆有這么一些好處：1.它是一個完全二叉樹，樹的深度是相同節點的二叉樹中最少的，維護效率較高；2.它可以通過數組來實現，而且父節點p與左右子節l，r點的數組下標的關系是s[l] = 2*s[p]+1和s[r] = 2*s[p]+2。在計算機中2*s[p]這樣的運算可以用一個左移1位操作來實現，十分高效。再加上數組可以隨機存取，效率也很高。3.堆的Extract操作，也就是將堆頂拿走並重新維護堆的時間復雜度是O（logn），這里n是堆的大小。 具體到我們的問題，如何具體實現呢？首先開辟一個大小為n的數組區A，從N中讀入n個數填入到A中，然後將A維護成一個小頂堆（即堆頂A[0]中存放的是A中最小的數）。然後從N中取出下一個數，即第n+1個數m，將m與堆頂A[0]比較，如果m<=A[0]，直接丟棄m。否則應該用m替換A[0]。但此時A的堆特性可能已被破壞，應該重新維護堆：從A[0]開始，將A[0]與左右子節點分別比較（特別注意，這里需要比較兩次才能確定最大數，在後面我會根據這個來和敗者樹比較），如果A[0]比左右子節點都小，則堆特性能夠保證，勿需繼續，否則如左（右）節點最大，則將A[0]與左（右）節點交換，並繼續維護左（右）子樹。依次執行，直到遍歷完N，堆中保留的n個數就是N中最大的n個數。 這都是堆排序的基本知識，唯一的trick就是維護一個小頂堆，而不是大頂堆。不明白的稍微想一下。維護一次堆的時間復雜度為O（logn），總體的復雜度是O（Nlogn）這樣一來，比起上面的O（nN），當n足夠大時，堆的效率肯定是要高一些的。當然，直接對N數組建堆，然後提取n次堆頂就能得到結果，而且其復雜度是O（nlogN）,當n不是特別小的時候這樣會快很多。但是對於online數據就沒辦法了，比如N不能一次load進內存，甚至是一個流，根本不知道N是多少。 敗者樹：有沒有別的演算法呢？我先來說一說敗者樹（loser tree）。也許有些人對loser tree不是很了解，其實它是一個比較經典的外部排序方法，也就是有x個已經排序好的文件，將其歸並為一個有序序列。敗者樹的思想咋一看有些繞，其實是為了減小比較次數。首先簡單介紹一下敗者樹：敗者樹的葉子節點是數據節點，然後兩兩分組（如果節點總數不是2的冪，可以用類似完全樹的結構構成樹），內部節點用來記錄左右子樹的優勝者中的敗者（注意記錄的是輸的那一方），而優勝者則往上傳遞繼續比較，一直到根節點。如果我們的優勝者是兩個數中較小的數，則根節點記錄的是最後一次比較中的敗者，也就是所有葉子節點中第二小的那個數，而最小的那個數記錄在一個獨立的變數中。這里要注意，內部節點不但要記錄敗者的數值，還要記錄對應的葉子節點。如果是用鏈表構成的樹，則內部節點需要有指針指向葉子節點。這里可以有一個trick，就是內部節點只記錄敗者對應的葉子節點，具體的數值可以在需要的時候間接訪問（這一方法在用數組來實現敗者樹時十分有用，後面我會講到）。關鍵的來了，當把最小值輸出後，最小值所對應的葉子節點需要變成一個新的數（或者改為無窮大，在文件歸並的時候表示文件已讀完）。接下來維護敗者樹，從更新的葉子節點網上，依次與內部節點比較，將敗者更新，勝者往上繼續比較。由於更新節點佔用的是之前的最小值的葉子節點，它往上一直到根節點的路徑與之前的最小值的路徑是完全相同的。內部節點記錄的敗者雖然稱為敗者，但卻是其所在子樹中最小的數。也就是說，只要與敗者比較得到的勝者，就是該子樹中最小的那個數（這里講得有點繞了，看不明白的還是找本書看吧，對照著圖比較容易理解）。 註：也可以直接對N構建敗者樹，但是敗者樹用數組實現時不能像堆一樣進行增量維護，當葉子節點的個數變動時需要完全重新構建整棵樹。為了方便比較堆和敗者樹的性能，後面的分析都是對n個數構建的堆和敗者樹來分析的。 總而言之，敗者樹在進行維護的時候，比較次數是logn+1。與堆不同的是，敗者樹是從下往上維護，每上一層，只需要和敗者節點比較一次即可。而堆在維護的時候是從上往下，每下一層，需要和左右子節點都比較，需要比較兩次。從這個角度，敗者樹比堆更優一些。但是，請注意但是，敗者樹每一次維護必定需要從葉子節點一直走到根節點，不可能中間停止；而堆維護時，有可能會在中間的某個層停止，不需要繼續往下。這樣一來，雖然每一層敗者樹需要的比較次數比堆少一倍，但是走的層數堆會比敗者樹少。具體少多少，從平均意義上到底哪一個的效率會更好一些？那我就不知道了，這個分析起來有點麻煩。感興趣的人可以嘗試一下，討論討論。但是至少說明了，也許堆並非是最優的。 具體到我們的問題。類似的方法，先構建一棵有n個葉子節點的敗者樹，勝出者w是n個中最小的那一個。從N中讀入一個新的數m後，和w比較，如果比w小，直接丟棄，否則用m替換w所在的葉子節點的值，然後維護該敗者樹。依次執行，直到遍歷完N，敗者樹中保留的n個數就是N中最大的n個數。時間復雜度也是O（Nlogn） 類快速排序方法： 快速排序大家大家都不陌生了。主要思想是找一個軸節點，將數列交換變成兩部分，一部分全都小於等於軸，另一部分全都大於等於軸，然後對兩部分遞歸處理。其平均時間復雜度是O（NlogN）。從中可以受到啟發，如果我們選擇的軸使得交換完的較大那一部分的數的個數j正好是n，不也就完成了在N個數中尋找n個最大的數的任務嗎？當然，軸也許不能選得這么恰好。可以這么分析，如果jn，則最大的n個數肯定在這j個數中，則問題變成在這j個數中找出n個最大的數；否則如果j<n，則這j個數肯定是n個最大的數的一部分，而剩下的j-n個數在小於等於軸的那一部分中，同樣可遞歸處理。 需要注意的是，這里的時間復雜度是平均意義上的，在最壞情況下，每次分割都分割成1：N-2，這種情況下的時間復雜度為O（n）。但是我們還有殺手鐧，可以有一個在最壞情況下時間復雜度為O（N）的演算法，這個演算法是在分割數列的時候保證會按照比較均勻的比例分割，at least 3n/10-6。具體細節我就不再說了，感興趣的人參考演算法導論（Introction to Algorithms 第二版第九章 Medians and Orders Statistics）。 還是那個結論，堆不見得會是最優的。 本文快要結束了，但是還有一個問題：如果N非常大，存放在磁碟上，不能一次裝載進內存呢？怎麼辦？對於介紹的Naive方法，堆，敗者樹等等，依然適用，需要注意的就是每次從磁碟上盡量多讀一些數到內存區，然後處理完之後再讀入一批。減少IO次數，自然能夠提高效率。而對於類快速排序方法，稍微要麻煩一些：分批讀入，假設是M個數，然後從這M個數中選出n個最大的數緩存起來，直到所有的N個數都分批處理完之後，再將各批次緩存的n個數合並起來再進行一次類快速排序得到最終的n個最大的數就可以了。在運行過程中，如果緩存數太多，可以不斷地將多個緩存合並，保留這些緩存中最大的n個數即可。由於類快速排序的時間復雜度是O（N），這樣分批處理再合並的辦法，依然有極大的可能會比堆和敗者樹更優。當然，在空間上會佔用較多的內存。 總結：對於這個問題，我想了很多，但是覺得還有一些地方可以繼續深挖：1. 堆和敗者樹到底哪一個更優？可以通過理論分析，也可以通過實驗來比較。也許會有人覺得這個很無聊；2. 有沒有近似的演算法或者概率演算法來解決這個問題？我對這方面實在不熟悉，如果有人有想法的話可以一塊交流。如果有分析錯誤或遺漏的地方，請告知，我不怕丟人，呵呵！最後請時刻謹記，時間復雜度不等於實際的運行時間，一個常數因子很大的O（logN）演算法也許會比常數因子小的O（N）演算法慢很多。所以說，n和N的具體值，以及編程實現的質量，都會影響到實際效率。

Ⅷ java演算法面試題

三個for循環，第一個和第二個有啥區別?去掉一個吧
可以用迭代器remove方法，在移除的同時添加。

不知道是你記錯了還是題本身就這樣，我只想說：
寫這代碼的是二貨么？
1、每個循環的索引都是從0開始，這是什麼遍歷方式？
2、看這題的目的是想把用戶添加到相應的組里，這我就不明白了，新建一個用戶的時候就沒分配組么？那用戶的GroupId哪來的？

3、這是一個操作，難道就不會根據GroupId直接查出用戶或者組么？

這哪是優化代碼？分明是挖坑。