Java面試題之手擼算法的示例分析

這篇文章將為大家詳細講解有關Java面試題之手擼算法的示例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

手擼算法1：查找數組中重復元素和重復元素的個數

當聽讓我寫這個算法時，紙筆還沒給到我手上，作為一個資深MySQL愛好者，瞬間從褲襠掏出一桿筆，打個哈欠的功夫，就在面試官臉上寫下了：

select num,count(num) from T group by num order by count(num) desc;

這個問題用的是數組，兩層循環比較或Map都可以解決，比較簡單，但是常問；方式如下：

1. 兩層循環比較方式

package com.softsec.demo;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
/**
 * 查找數組中重復元素和重復元素的個數
 * @author chenhh
 *
 */
public class getRepeat {
	/**
	 * 循環比較處理
	 * @param arr
	 */
	public static void cyclingDemo ( int[] arr){
		for (int x = 0; x < 10; x++) {
			int sumber1 = 0;
			for (int j = 0; j < 20; j++) {
				//數組中的數循環比較
				if (x == arr[j]) {
					sumber1++;
				} else {
					continue;
				}
			}
			System.out.println(x + " -- 重復個數:" + sumber1);
		}
	}
	public static void main (String[] args){
		Random random = new Random();
		int[] arr = new int[20];
		for (int i = 0; i < 20; i++) {
			arr[i] = random.nextInt(10);
			if (i < arr.length - 1) {
				System.out.print(arr[i]+"，");
			} else {
				System.out.print(arr[i] + "\r\n 結果：" + "\r\n" );
			}
		}
		// 輸出arr數組中重復元素，重復數量
		// 循環處理
		cyclingDemo(arr);
		// map處理
		// mapDemo(arr);
	}

打印結果：

0，3，4，0，6，5，8，1，3，1，9，3，6，3，7，5，7，1，1，1
結果：
0 -- 重復個數:2
1 -- 重復個數:5
2 -- 重復個數:0
3 -- 重復個數:4
4 -- 重復個數:1
5 -- 重復個數:2
6 -- 重復個數:2
7 -- 重復個數:2
8 -- 重復個數:1
9 -- 重復個數:1

Process finished with exit code 0

2. 轉成Map集合處理方式

package com.softsec.demo;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
/**
 * 查找數組中重復元素和重復元素的個數
 * @author chenhh
 *
 */
public class getRepeat {
	/**
	 * 轉成集合處理
	 * @param arr
	 */
	public static void mapDemo ( int[] arr){
		//將數據轉成集合
		Map<Integer, Integer> map = new HashMap();
		for (int a = 0; a < arr.length; a++) {
			if (map.get(arr[a])!=null){
				map.put(arr[a],map.get(arr[a])+1);
			}
			else {
				map.put(arr[a],1);
			}
		}
		for (int i = 0; i <10 ; i++) {
			System.out.println(i + " -- 重復個數：" + map.get(i));
		}
	}
}

	public static void main (String[] args){
		Random random = new Random();
		int[] arr = new int[20];
		for (int i = 0; i < 20; i++) {
			arr[i] = random.nextInt(10);
			if (i < arr.length - 1) {
				System.out.print(arr[i]+"，");
			} else {
				System.out.print(arr[i] + "\r\n 結果：" + "\r\n" );
			}
		}
		// 輸出arr數組中重復元素，重復數量
		// 循環處理
		// cyclingDemo(arr);
		// map處理
		mapDemo(arr);
	}
}

打印結果：

2，2，7，7，1，6，1，7，1，9，1，2，1，9，9，4，0，3，5，1
結果：
0 -- 重復個數：1
1 -- 重復個數：6
2 -- 重復個數：3
3 -- 重復個數：1
4 -- 重復個數：1
5 -- 重復個數：1
6 -- 重復個數：1
7 -- 重復個數：3
8 -- 重復個數：null
9 -- 重復個數：3

Process finished with exit code 0

手擼算法2：寫個二分查找demo吧

二分查找的條件是對一組有序數組的查找，所以要先確定查找的數組是否有序，在使用二分查找的時候先要對數組進行排序。

加個排序多麻煩？所以面試官不指定無序數組時，就都當有序的就行。無序你用什么二分法是吧？

二分算法步驟

1.首先確定整個查找區間的中間位置mid = （ left + right ）/ 2

2.用待查關鍵字值與中間位置的關鍵字值進行比較；

★ 若相等，則查找成功

★ 若大于，則在后（右）半個區域繼續進行折半查找

★ 若小于，則在前（左）半個區域繼續進行折半查找

3.對確定的縮小區域再按折半公式，重復上述步驟，使用遞歸或普通while循環都可以。

這里我們對給定數列（有序）{ 1, 20, 23, 24, 35, 46, 77, 78, 99, 100}，通過二分法查找值為78的數據元素。

package com.softsec.demo;
/**
 * 二分查找算法，兩種方法，一種遞歸一種非遞歸
 * @author chenhh
 *
 */
public class BinaryQry {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = new int[] { 1, 20, 23, 24, 35, 46, 77, 78, 99, 100 };
		int index = search(arr,0,arr.length-1,78);
		//int index = search3(arr, 11);
		if (index == -1) {
			System.out.println("沒找到");
			return;
		}
		System.out.println("在數組的第" + (index+1) + "位");
	}
	/*
	 * 遞歸方法查找
	 */
	public static int search(int[] arr, int left, int right, int key) {
		if (left <= right) {
			int mid = (left + right) / 2;
			if (key < arr[mid]) {
				return search(arr, left, mid - 1, key);
			} else if (key > arr[mid]) {
				return search(arr, mid + 1, right, key);
			} else {
				return mid;
			}
		}
		return -1;
	}
	/*
	 * 非遞歸方法查找
	 */
	public static int search3(int[] arr, int key) {
		int left = 0;
		int right = arr.length - 1;
		int mid = 0;
		while (left <= right) {
			mid = (left + right) / 2;
			if (key == arr[mid]) {
				return mid;
			} else if (key > arr[mid]) {
				left = mid + 1;
			} else if (key < arr[mid]) {
				right = mid - 1;
			}
		}
		return -1;
	}
}

手擼算法3：把兩個有序數組合并成一個有序數組

對于兩個有序數組arrayM，arrayN，數組長度分別為m和n；

思路：

• 定義一個新數組newArray，長度為m+n；

• 定義兩個index（int），如：int start=0,end=0，用來記錄數組arrayM、arrayN的下標；

• 通過分別遍歷數組arrayM和arrayN的方式來比較每個值的大小，并將值存放到newArray中；

• 判斷start和end是否分別小于m和n，如果小于則繼續執行，否則則表示有一個array遍歷結束，然后將另一個array剩余部分追加到newArray中即可；

package com.softsec.demo;
/**
 * 兩個有序數組合并成一個有序數組的實現類
 * @author chenhh
 *
 */
public class ArrayMerge {
	/**
	* 數組合并方法
	* @param arrayM
	* @param arrayN
	* @return
	*/
	public static int[] mergeArray(int arrayM[],int arrayN[]){
		int newArray[];
		// 定義一個新數組，長度為兩個有序數組長度之和
		newArray = new int[arrayM.length + arrayN.length];
		// start:arrayM數組下標    end：arrayN數組下標  k：newArray新數組下標
		int start=0,end=0,k=0;
		// 循環比較兩個數組，較小元素的放入新數組，較小元素所在數組下標加一，較大元素對應的數組下標不加一，直到某一個下標等于數組長度時退出循環
		while(start<arrayM.length && end<arrayN.length) {
			if(arrayM[start] <= arrayN[end]) {
				newArray[k++] = arrayM[start++];
			}else{
				newArray[k++] = arrayN[end++];
			}
		}
		/* 后面兩個while循環是用來保證兩個數組比較完之后剩下的一個數組里的元素能順利都放入新數組
		* 此時較短數組已經全部放入新數組，較長數組還有部分剩余，最后將剩下的部分元素放入新數組，因為數組是有序，所以直接把剩下的順序加入即可*/
		while(start < arrayM.length) {
			newArray[k++] = arrayM[start++];
		}
		while(end < arrayN.length) {
			newArray[k++] = arrayN[end++];
		}
		return newArray;
	}
	/**
	* 數組打印方法
	* @param arr
	*/
	public static void print(int[] arr) {
		for(int i=0; i<arr.length;i++) {
			if (i < arr.length -1) {
				System.out.print(arr[i]+"，");
			} else {
				System.out.print(arr[i]);
			}
		}
	}
	public static void main(String[] args) {
		int[] arrayM = {1,3,5,7,8,9,14,16,21};
		int[] arrayN = {0,10,20,30,40,50};
		print(mergeArray(arrayM,arrayN));
	}
}

結果打印：

0，1，3，5，7，8，9，10，14，16，20，21，30，40，50
Process finished with exit code 0

關于“Java面試題之手擼算法的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。