JZ63 資料流中的中位數
（中等）
題目
描述
如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那麼中位數就是所有數值排序之後位于中間的數值。如果從資料流中讀出偶數個數值，那麼中位數就是所有數值排序之後中間兩個數的平均值。我們使用Insert()方法讀取資料流，使用GetMedian()方法擷取目前讀取資料的中位數。
示例
輸入：
[5,2,3,4,1,6,7,0,8]
傳回值：
"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
說明：
資料流裡面不斷吐出的是5,2,3…,則得到的平均數分别為5,(5+2)/2,3…
思路
（我對題意建議：這道題，上來看到了“資料流”這個詞，我的直接反應就是怎麼遇到了一個用I/O流的題，太少見了，是用資料流在背景算法中讀資料嗎？但之後才發現我I/O資料流沒關系，我認為出題人很不注重措辭的嚴謹性，用“數組”，或者“序列”多好呢）
這道題我想到的第一種算法就是用直接插入排序來解決，因為求序列的中位數的前提是要求序列有序，而使得序列有序的操作對于此題來說，可以放在Insert()方法中實作——即在插入時就按有序比較來插入，也可以放在GetMedian()方法中——即僅每次求中位數時，才對序列進行排序，之後求中位數，所有由于我想到的是直接插入排序，是以自然就将排序的工作和插入的工作放在一起來做了，也就是前一種方法，在Insert()方法中實作，其他内容也沒必要闡述了，直接插入排序無非就是将待插入值先與序列中各值進行比較，找到插入點，後移插入點及其之後元素，将待插入值插入插入點即可（詳細解析請看之前文章：Java實作七種【排序算法】+圖解+完整代碼+分析）
在做完後，發現此題還有一種解法，用堆排序去實作，用一個小根堆維護中位數及其左邊的元素，用一個大根堆維護中位數及其右邊的元素，最後的中位數，則為這兩個大小根堆的根結點的值其中的一個或是兩個的平均值（奇偶個數不确定）。
實作
public class Solution {
double[] nums = new double[101];
int len = 0;
public void Insert(Integer num) {
boolean flag = false;
for (int i = 0; i < len; i++) {
if (num <= nums[i]) {
for (int j = len; j >= i; j--) {
nums[j + 1] = nums[j];
}
nums[i] = num;
flag = true;
len++;
break;
}
}
if (!flag) {
nums[len++] = num;
}
}
public Double GetMedian() {
if (len % 2 == 0) {
return (nums[len / 2 - 1] + nums[len / 2]) / 2;
} else {
return nums[len / 2];
}
}
} 
JZ65 矩陣中的路徑
（中等）
題目
描述
【算法】解題總結：劍指Offer 63 資料流中的中位數、劍指Offer 65 矩陣中的路徑 示例【算法】解題總結：劍指Offer 63 資料流中的中位數、劍指Offer 65 矩陣中的路徑
我的解法——思路正确，代碼報錯
這是一道迷宮問題，首先判斷傳入的數組是否為空值，增加容錯性，在兩次 for 循環中，将每個點都嘗試作為起點，直到成功，同時本着不破壞原數組的前提下，每次建立一個複制數組，來進行接下來需要改變數組中值的操作（如走過，就标記 ‘#’），遞歸操作每個起點開始的迷宮數組，若碰到邊界，或是走過，就傳回 false，如果目前值與待配對值不相等，也傳回 false，如果相等，同時又比對了最後一個字元，那麼傳回 true，如果仍需比對，那麼再從此點進行上下左右的遞歸比對，同時因本次的成功比對，用于記錄目前比對位置的下标也應右移。
public class Solution {
char[] wordArray = null; //存儲字元串word
int rowNum = 0;
int colNum = 0;
public char[][] copyDeepChar(char[][] matrix) {
if (matrix == null || matrix.length == 0
|| word == null || word.length() == 0) {
return false;
}
char[][] copy = new char[rowNum][colNum];
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
copy[i][j] = matrix[i][j];
}
}
return copy;
}
public boolean hasPath (char[][] matrix, String word) {
this.wordArray = word.toCharArray();
this.rowNum = matrix.length;
this.colNum = matrix[0].length;
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
//每次都要複制一次，因為每次都會因走過為标記 '#'
char[][] myMatrix = copyDeepChar(matrix);
if (dfs(myMatrix, i, j, 0)) {
return true;
}
}
}
return false;
}
public boolean dfs(char[][] myMatrix, int i, int j, int index) {
//出界，或走過
if (i < 0 || i >= rowNum || j < 0 || j >= colNum || myMatrix[i][j] == '#') {
return false;
}
//不相等
if (myMatrix[i][j] != wordArray[index]) {
return false;
}
//比對成功
if (index == wordArray.length - 1) {
return true;
}
//相等，移動下标
index++;
myMatrix[i][j] = '#'; //表示已經走過
return dfs(myMatrix, i + 1, j, index + 1) || dfs(myMatrix, i - 1, j, index + 1)
|| dfs(myMatrix, i, j - 1, index + 1) || dfs(myMatrix, i, j + 1, index + 1);
}
} 之後學習了别人的實作
學習自：https://blog.nowcoder.net/n/3ef094bfeb0244e59a40340963fc1eab?f=comment
這段正确的代碼，和我想的思路是大體相同的，但是我的送出報錯，我并沒有找到問題在哪