堆的代码实现：
需要明确的是：二叉堆虽然是一颗完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。即二叉堆的所有节点都存储在数组当中。
问题是：在数组中，在没有左右指针的情况下，如何定位到一个父节点的左孩子和右孩子呢？
答：像图中那样，可以依靠数组下标来计算。
假设父节点的下标是parent，那么它的左孩子下标就是2*parent+1；它的右孩子下标就是2*parent+2。
比如上面的例子中，节点6包含9和10两个孩子，节点6在数组中的下标是3，节点9在数组中的下标是7，节点10在数组中的下标是8。
7 = 3 ∗ 2 + 1 7=3*2+1 7=3∗2+1
8 = 3 ∗ 2 + 2 8=3*2+2 8=3∗2+2
刚好符合规律。代码如下：
import java.util.Arrays;public class HeapOperator {/*** 上浮调整** @param array 待调整的堆*/public static void upAdjust(int[] array) {int childIndex = array.length - 1; // 插入的节点一定是左孩子,即lChild=2*parent+1int parentIndex = (childIndex - 1) / 2;// temp保存插入的叶子节点值，用于最后的赋值int temp = array[childIndex];while (childIndex > 0 && temp < array[parentIndex]) {//无需真正交换，单向赋值即可array[childIndex] = array[parentIndex];childIndex = parentIndex;parentIndex = (parentIndex - 1) / 2; // ？？}array[childIndex] = temp;}/*** 下沉调整** @param array 待调整的堆* @param parentIndex 要下沉的父节点* @param length 堆的有效大小*/public static void downAdjust(int[] array, int parentIndex, int length) {// temp 保存父节点的值，用于最后的赋值int temp = array[parentIndex];int childIndex = 2 * parentIndex + 1;while (childIndex < length) {//如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {childIndex++;}//如果父节点小于任何一个孩子的值，直接跳出if (temp <= array[childIndex])break;//无需真正交换，单向赋值即可array[parentIndex] = array[childIndex];parentIndex = childIndex;childIndex = 2 * parentIndex + 1;}array[parentIndex] = temp;}/*** 构建堆** @param array 待调整的堆*/public static void buildHeap(int[] array) {//从最后一个非叶子节点开始，依次下沉调整for (int i = array.length / 2; i >= 0; i--) {downAdjust(array, i, array.length - 1);}}public static void main(String[] args) {int[] array = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};upAdjust(array);System.out.String(array));array = new int[]{7, 1, 3, 10, 5, 2, 6, 8, 9};buildHeap(array);System.out.String(array));}
}代码中有一个优化的点，就是父节点和孩子节点做连续交换时，并不一定要真的交换，只需要先把交换一方的值存入temp变量，做单向覆盖，循环结束后，再把temp的值存入交换后的最终位置。
二叉堆的用处：是实现堆排序以及优先级队列的基础。
import java.util.Arrays;public class HeapSort {public static void main(String[] args) {int[] arr = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};heapSort(arr);System.out.String(arr));}/*** 堆排序** @param array 待调整的堆*/private static void heapSort(int[] array) {// 1. 把无序数组构建成二叉堆for (int i = (array.length - 2) / 2; i >= 0; i--) {downAdjust(array, i, array.length);}System.out.String(array));// 2. 循环删除堆顶元素，移到集合尾部，调整堆产生新的堆顶。for (int i = array.length - 1; i > 0; i--) {// 最后一个元素和第一个元素交换int temp = array[i];array[i] = array[0];array[0] = temp;//下沉调整最大堆downAdjust(array, 0, i);}}/*** 下沉调整** @param array 待调整的堆* @param parentIndex 要下沉的父节点* @param length 堆的有效大小*/private static void downAdjust(int[] array, int parentIndex, int length) {// temp保存父节点值，用于最后的赋值int temp = array[parentIndex];int childIndex = 2 * parentIndex + 1;while (childIndex < length) {//如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {childIndex++;}//如果父节点大于任何一个孩子的值，直接跳出if (temp >= array[childIndex])break;//无需真正交换，单向赋值即可array[parentIndex] = array[childIndex];parentIndex = childIndex;childIndex = 2 * childIndex + 1;}array[parentIndex] = temp;}
}
class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}public class TreeDepth {public int treeDepth(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}//左右子树高度中取较高的那一个高度+1return treeDepth(root.left) > treeDepth(root.right) ? treeDepth(root.left) + 1 : treeDepth(root.right) + 1;}
}
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;public class TopK {public static List<Integer> solutionByHeap(int[] input, int k) {List<Integer> list = new ArrayList<>();if (k > input.length || k == 0) {return list;}Queue<Integer> queue = new PriorityQueue<>();for (int num : input) {if (queue.size() < k) {queue.add(num);} else if (queue.peek() < num) {queue.poll();queue.add(num);}}while (k-- > 0) {list.add(queue.poll());}return list;}
}
当然，如果是求前 K 个最小的数，只需要改为大顶堆即可
if(root==null){return;
}
然后声明一个临时变量用来存储两个节点交换的值，然后进行左右子树交换。
//进行节点交换
Let tempNode = root.left;
root.left = root.right;
root.right = tempNode;
交换之后，直接递归剩下的节点进行交换就OK。然后返回递归后的树的根节点。
//递归遍历剩余的子节点
insert(root.left)
insert(root.right)//返回根节点
return root;
完整代码如下：
public class TreeMirror {public static void mirror(TreeNode root) {//如果根节点为空，无需处理if (root == null) {return;}//左子节点和右子节点都为空，无需处理if (root.left == null && root.right == null) {return;}//左子节点不为空，则对该子节点做镜像处理if (root.left != null) {mirror(root.left);}//右子节点不为空，则对该子节点做镜像处理if (root.right != null) {mirror(root.right);}//交换当前节点的左右子节点位置TreeNode temp = root.left;root.left = root.right;root.right = temp;}
}
方法2：首先创建一个以节点ID为键的HashSet集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和HashSet集合当中存储的节点作比较，如果发现HashSet当中存在相同节点ID，则说明链表有环；如果HashSet当中不存在相同的节点ID，就把这个新节点的ID存入HashSet，之后进入下一个节点，继续重复刚才的操作。
这个方法在流程上和方法一类似，本质的区别是使用了HashSet作为额外的缓存。
假设从链表头节点到入环点的距离是D，链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S)=D+S，可以简单理解为O(N)。而算法的空间复杂度还是D+S-1，可以简单地理解成O(N)。
方法3：首先创建两个指针1和2（在java里就是两个对象的引用），同时指向这个链表的头节点，然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同，如果相同，则判断出链表有环，如果不同，则继续下一次循环。
例如链表A->B->C->D->B->C->D，两个指针最初都指向节点A，进入第一轮循环，指针1移动到了节点B，指针2移动到了C。第二轮循环，指针1移动到了节点C，指针2移动到了节点B。第三轮循环，指针1移动到了节点D，指针2移动到了节点D，此时两指针指向同一节点，判断出链表有环。
此方法也可以用一个更生动的例子来形容：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。
假设从链表头节点到入环点的距离是D，链表的环长是S。那么循环会进行S次（为什么是S次，有心的同学可以自己揣摩下），可以简单理解为O（N）。除了两个指针以外，没有使用任何额外存储空间，所以空间复杂度是O（1）。
|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
补充问题：
问题1：判断两个单向链表是否相交，如果相交，求出交点。
答：注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
由于链表本身的性质，如果有一个结点相交，那么相交结点之后的所有结点都是这两个链表共用的，也就是说两个链表的长度主要相差在相交结点之前的结点长度，于是我们有以下思路：
1）如果链表没有长度，则我们先遍历这两个链表拿到两个链表长度，假设分别为L1,L2(L1>=L2),定义p1,p2指针分别指向各自链表head结点，然后p1先往前走L1-L2步。这一步保证了p1,p2指向的指针与相交节点（如果有的话）一样近。
2）然后 p1,p2 不断往后遍历，每次走一步，边遍历边判断相应结点是否相等，如果相等即为这两个链表的相交结点。
问题2：在一个有环链表中，如何找出链表的入环点？
答：继续用快慢指针来解决，如下所示：
H: 链表头； A: 入环点 ；B: 快慢指针相交点
先做如下约定：
LHA: 链表头H到入环点A的距离;
LAB: 链表节点A顺时针到节点B的距离;
LBA: 链表节点B顺时针到节点A的距离;
根据移动距离,可知:
2慢指针移动距离 = 快指针移动距离，即2(LHA + LAB) = LHA + LAB + LBA + LAB;
最后推导出：LHA = LBA
所以,只要从相交点和头节点同时遍历到的相同节点就能找到入环点.
代码如下：
import java.util.HashSet;
import java.util.Set;public class CycleListNode {static class ListNode {int val;ListNode next;public ListNode(int data) {this.val = data;}}/*** 快慢指针*/public static boolean hasCycleByPoint(ListNode head) {boolean hasCycle = true;ListNode fastIndex = head;ListNode slowIndex = head;do {if (fastIndex == null) {hasCycle = false;break;}if ( == null) {hasCycle = false;break;}fastIndex = ;slowIndex = ;} while (fastIndex != slowIndex);return hasCycle;}/*** hash*/public static boolean hasCycleByHash(ListNode head) {boolean hasCycle = false;Set set = new HashSet();while (head != null) {if (ains(head)) {hasCycle = true;break;}set.add(head);head = ;}return hasCycle;}/*** 单链表第一个相交点* @param head1* @param head2* @return*/public static ListNode getFirstCommonNode(ListNode head1, ListNode head2) {int length1 = 0; //链表1的长度int length2 = 0; //链表2的长度ListNode p1 = head1;ListNode p2 = head2;while (p1.next != null) {length1++;p1 = p1.next;}while (p2.next != null) {length2++;p2 = p2.next;}p1 = head1;p2 = head2;//p1或p2前进|length1-length2|步if (length1 >= length2) {int diffLen = length1 - length2;while (diffLen > 0) {p1 = p1.next;diffLen--;}} else {int diffLen = length2 - length1;while (diffLen > 0) {p2 = p2.next;diffLen--;}}//p1,p2分别往后遍历，边遍历边比较，如果相等，即为第一个相交节点while (p1 != null && p2.next != null) {p1 = p1.next;p2 = p2.next;if (p1.val == p2.val) {//p1，p2都为相交节点，返回p1或p2return p1;}}//如果没有相交节点，返回空指针return null;}/*** 环形相交点* F:头结点到入环结点距离* B:入环结点到快慢指针相交结点距离* C:快慢指针相交结点到入环结点距离* 2*慢指针移动距离=快指针移动距离* 2(F+B)=F+B+B+C* F = C** @param head* @return*/public static ListNode getEntranceNode(ListNode head) {ListNode fastIndex = head;ListNode slowIndex = head;do {if (fastIndex == null) {break;}if ( == null) {fastIndex = ;break;}fastIndex = ;slowIndex = ;} while (fastIndex != slowIndex);if (fastIndex == null) {return null;}ListNode headIndex = head;while (fastIndex != headIndex) {fastIndex = ;headIndex = ;}return fastIndex;}public static void main(String[] args) {test1();test2();test3();}private static void test1() {ListNode n1 = new ListNode(1);ListNode n2 = new ListNode(2);ListNode n3 = new ListNode(3);ListNode n4 = new ListNode(4);ListNode n5 = new ListNode(5);n1.next = = = = = n2;System.out.println(hasCycleByPoint(n1));assert getEntranceNode(n1) != null;System.out.println(getEntranceNode(n1).val);}private static void test2() {ListNode n1 = new ListNode(1);ListNode n2 = new ListNode(2);ListNode n3 = new ListNode(3);ListNode n4 = new ListNode(4);ListNode n5 = new ListNode(5);n1.next = = = = n5;System.out.println(hasCycleByPoint(n1));System.out.println(getEntranceNode(n1));}private static void test3() {ListNode n1 = new ListNode(1);ListNode n2 = new ListNode(2);ListNode n3 = new ListNode(3);ListNode n4 = new ListNode(4);ListNode n5 = new ListNode(5);n1.next = = = = n5;System.out.println(getFirstCommonNode(n1, n2).val);}
}|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
/*** 迭代翻转*/
public void iterationInvertLinkedList() {// 步骤 1Node pre = ;Node cur = ; = null;while (cur != null) {/*** 务必注意：在 cur 指向 pre 之前一定要先保留 cur 的后继结点，不然 cur 指向 pre 后就再也找不到后继结点了* 也就无法对 cur 后继之后的结点进行翻转了*/Node next = ; = pre;pre = cur;cur = next;}// 此时 pre 为头结点的后继结点 = pre;
}
用迭代的思路来做由于循环了 n 次，显然时间复杂度为 O(n)，另外由于没有额外的空间使用，也未像递归那样调用递归函数不断压栈，所以空间复杂度是 O(1),对比递归，显然应该使用迭代的方式来处理！
完整代码如下：
public class LinkedList {int length = 0; //链表长度，非必须Node head = new Node(0); //哨兵节点public void addNode(int val) {Node tmp = head;while ( != null) {tmp = ;} = new Node(val);length++;}public void printList() {head = ;do {System.out.println(head.data);head = ;} while (this.head != null);}public void headInsert(int val) {// 1. 构造新节点Node newNode = new Node(val);//2. 新节点指向头节点之后的节点 = ;// 3. 头节点指向新节点 = newNode;length++;}/*** 删除指定的结点** @param deletedNode*/public void removeSelectedNode(Node deletedNode) {// 如果此结点是尾结点，我们还是要从头节点遍历到尾结点的前继结点，再将尾结点删除if ( == null) {Node tmp = head;while ( != deletedNode) {tmp = ;}//找到尾结点的前继结点 = null;} else {Node nextNode = ;//将删除结点的后继节点的值赋给被删除结点deletedNode.data = nextNode.data;//将nextNode结点删除 = ; = null;}}/*** 递归翻转结点node开始的链表** @param node* @return*/public Node invertLinkedList(Node node) {if ( == null) {return node;}// 步骤1：先翻转node之后的链表Node newHead = );// 步骤2：再把原node节点后继节点的后继节点指向node(4)，node的后继节点设置为空（防止形成环&#ext = = null;// 步骤3：返回翻转后的头节点return newHead;}/*** 迭代式翻转链表*/public void iterationInvertLinkedList() {// 步骤1Node pre = ;Node cur = ; = null;while (cur != null) {//在cur指向pre之前一定要先保留cur和后继结点Node next = ; = pre;pre = cur;cur = next;}// 此时pre为头结点的后继结点 = pre;}public static void main(String[] args) {LinkedList linkedList = new LinkedList();int[] arr = {4, 3, 2, 1};//头插发构造链表for (int i = 0; i < arr.length; i++) {linkedList.addNode(arr[i]);}Node newHead = linkedList.invertLinkedList();//翻转后别忘了设置头结点的后继结点 = newHead;//打印链表linkedList.printList();}
}package DataStructure;import java.util.Stack;public class StackforQueue {private Stack<Integer> stackA = new Stack<>();private Stack<Integer> stackB = new Stack<>();/*** 入队操作** @param element*/private void enQueue(int element) {stackA.push(element);}/*** 出队操作** @return*/private Integer deQueue() {if (stackB.isEmpty()) {if (stackA.isEmpty()) {return null;}transfer();}return stackB.pop();}/*** 将栈A的元素转移到栈B*/private void transfer() {while (!stackA.isEmpty()) {stackB.push(stackA.pop());}}public static void main(String[] args) {StackforQueue stackforQueue = new StackforQueue();Queue(1);Queue(2);Queue(3);System.out.println(stackforQueue.deQueue());System.out.println(stackforQueue.deQueue());Queue(4);System.out.println(stackforQueue.deQueue());System.out.println(stackforQueue.deQueue());}
}入队的时间复杂度显然是O(1)。至于出队操作，如果涉及到栈A和栈B的元素迁移，时间复杂度为O(n)，如果不用迁移，时间复杂度为O(1)。
package DataStructure;public class Exchange {public static void main(String[] args) {int numa = -3;int numb = -9;int[] num = exchange3(numa, numb);System.out.println(num[0] + " " + num[1]);}/*** 利用异或交换* @param numa* @param numb* @return*/private static int[] exchange1(int numa, int numb) {int[] num = new int[2];numa = numa ^ numb;numb = numa ^ numb;numa = numa ^ numb;num[0] = numa;num[1] = numb;return num;}/*** 利用加减法交换* @param numa* @param numb* @return*/public static int[] exchange2(int numa, int numb) {int[] num = new int[2];numa = numa + numb;numb = numa - numb;numa = numa - numb;num[0] = numa;num[1] = numb;return num;}/*** 利用乘除法交换* 注意，除数不能为0* @param numa* @param numb* @return*/public static int[] exchange3(int numa, int numb) {int[] num = new int[2];numa = numa * numb;numb = numa / numb;numa = numa / numb;num[0] = numa;num[1] = numb;return num;}/*** 有符号的数值交换* @param numa* @param numb* @return*/public static int[] exchange4(int numa, int numb) {int[] num = new int[2];// 不同符号if (numa * numb <= 0) {numa = numa + numb;numb = numa - numb;numa = numa - numb;} else {numa = numa - numb;numb = numa + numb;numa = numb - numa;}num[0] = numa;num[1] = numb;return num;}
}另外不使用异或的方法存在一些问题，例如①使用中间变量，这种方法需要利用额外的空间存储变量，②使用加减法或乘除法，可能造成溢出。
补充问题：在一个数组中找出唯一一个与数组内任何元素都不相等的一个元素？
答：可以使用异或运算来达到目的，因为问题的前提是数组内只含有一个不与其他元素重复的元素，那么我们便可以利用异或运算的特点来解决此问题。因为相同的元素经过异或运算的结果是0，那么我们**遍历数组内所有的元素，它们进行异或运算，最终得出的结果便是那个唯一不与其他元素重复的元素。**时间复杂度为O(N)。
import java.util.Arrays;
import java.util.List;/*** 创建最大堆，并进行排序*/
public class HeapSortAdvance {public static void main(String[] args) {HeapSortAdvance hsa = new HeapSortAdvance();List<Integer> list = null;list = Arrays.asList(3, 0, 23, 6, 5, 43, 23, 566, 67, 34, 2, 56, 98, 42, 49);ateHeap(list);hsa.sort(list);for (int i = 0; i < list.size(); i++) {System.out.(i) + " ");}}/*** 创建堆，从第一个非孩子结点开始调整，创建一个最大堆** @param list*/private List<Integer> createHeap(List<Integer> list) {int n = list.size();for (int k = (n - 1) / 2; k >= 0; k--) {shiftDown(list, k, n - 1);}return list;}/*** 将以parent为根节点的二叉树调整为堆** @param list* @param parent* @param end*/private void shiftDown(List<Integer> list, int parent, int end) {boolean flag = true;while (parent * 2 + 1 <= end && flag) { // 如果存在左孩子就进行调整int lchild = parent * 2 + 1;int max = 0;if (lchild + 1 <= end) { //表示存在右孩子int rchild = lchild + 1;max = (lchild) > (rchild) ? lchild : rchild;} else {max = lchild;}if ((max) > (parent)) { //有孩子比父亲大swap(list, max, parent);parent = max;} else {flag = false; //表示孩子都比父亲大，不需要调整了}}}private void swap(List<Integer> list, int m, int n) {int temp = (n);list.set(n, (m));list.set(m, temp);}public void sort(List<Integer> heap) { //排序主过程int n = heap.size();int rmd = n - 1;while (rmd > 0) {swap(heap, 0, rmd);shiftDown(heap, 0, rmd - 1);rmd--;}}
}public class MyClass {public static void main(String[] args) {int[] num1 = new int[]{1, 2, 4, 6, 7, 123, 411, 5334, 1414141, 1314141414};int[] num2 = new int[]{0, 2, 5, 7, 89, 113, 5623, 6353, 134134};//变量用于存储两个集合应该被比较的索引（存入新集合就加一）int a = 0;int b = 0;int[] num3 = new int[num1.length + num2.length];for (int i = 0; i < num3.length; i++) {if (a < num1.length && b < num2.length) { //两数组都未遍历完，相互比较后加入if (num1[a] > num2[b]) {num3[i] = num2[b];b++;} else {num3[i] = num1[a];a++;}} else if (a < num1.length) { //num2已经遍历完，无需比较，直接将剩余num1加入num3[i] = num1[a];a++;} else if (b < num2.length) { //num1已经遍历完，无需比较，直接将剩余num2加入num3[i] = num2[b];b++;}}System.out.println("排序后:" + String(num3));}
}
然后，我们考虑如何合并K个有序数组。最简单的方法是创建一个N大小的数组，然后把所有的数字拷贝进去，然后在进行时间复杂度为O(NlogN)的排序算法，这样总体时间复杂度为O(NlogN)。除此之外，可以利用最小堆完成。时间复杂度为O(NlogK)，具体过程如下：
①创建一个大小为N的数组保存最后的结果
②数组本身已经是从大到小的排序，所以我们只需要创建一个大小为K 的最小堆，堆中的初始元素为K个数组中的每个数组的第一个元素，每次从堆中取出最小元素（堆顶元素），并将其存入输出数组中，将堆顶元素所在行的下一个元素加入堆，重新排列堆顶元素，时间复杂度为logK，总计N个元素，所以总体时间复杂度是NlogK
在O(NlogK)的时间复杂度内完成：
package DataStructure;import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;class Element {public int row, col, val;Element(int row, int col, int val) {w = l = col;this.val = val;}
}public class MergeTwoArray {public static void main(String[] args) {//定义K个一维数组int[][] array = {{1, 4, 7, 8, 12, 16, 20}, {2, 5, 7, 9, 10, 25}, {3, 6, 11, 13, 17, 18}};int[] merged = mergedKSortedArray(array); // 使用最小堆int[] merged2 = mergedKSortedArray2(array); //使用归并法System.out.String(merged));System.out.String(merged2));}/*** 方法1：使用最小堆* @param array* @return*/private static int[] mergedKSortedArray(int[][] array) {if (array == null) {return new int[0];}int totalSize = 0;//默认由小到大排序Queue<Element> queue = new PriorityQueue<Element>(array.length, ElementComparator);//初始化//把每一行的第一个元素加入PriorityQueue//统计元素总量for (int i = 0; i < array.length; i++) {//当前行长度不为0if (array[i].length > 0) {Element element = new Element(i, 0, array[i][0]);queue.add(element);totalSize += array[i].length;}}int[] result = new int[totalSize];int index = 0;while (!queue.isEmpty()) {Element element = queue.poll();result[index++] = element.val;//当前结点被PriorityQueue跑出来后，当前行的第二个结点加入PriorityQueueif (l + 1 < w].length) {l += 1;element.val = w][l];queue.add(element);}}return result;}private static Comparator<Element> ElementComparator = new Comparator<Element>() {@Overridepublic int compare(Element left, Element right) {return left.val - right.val;}};/*** 方法2：使用分治法下的归并* @param array* @return*/private static int[] mergedKSortedArray2(int[][] array) {if (array == null) {return new int[0];}return helper(array, 0, array.length - 1);}private static int[] helper(int[][] array, int l, int r) {if (l == r) {return array[l];}if (l + 1 == r) {return merged2Array(array[l], array[r]);}int mid = l + (r - l) / 2;int[] left = helper(array, l, mid);int[] right = helper(array, mid + 1, r);return merged2Array(left, right);}private static int[] merged2Array(int[] a, int[] b) {int[] res = new int[a.length + b.length];int i = 0, j = 0;for (int k = 0; k < res.length; k++) {if (i >= a.length) {res[k] = b[j++];} else if (j >= b.length) {res[k] = a[i++];} else if (a[i] < b[j]) {res[k] = a[i++];} else {res[k] = b[j++];}}return res;}
}package DataStructure;import java.util.Arrays;public class SortPringMatrix {public static void main(String[] args) {int[][] matrix = {{57, 50, 59, 18, 31, 13},{67, 86, 93, 86, 4, 9},{38, 98, 83, 56, 82, 90},{66, 50, 67, 11, 7, 69},{20, 58, 55, 24, 66, 10},{43, 26, 65, 0, 64, 28},{62, 86, 38, 19, 37, 98}};int[] res = printMatrix(matrix);System.out.String(res));}private static int[] printMatrix(int[][] matrix) {int rows = matrix.length;int cols = matrix[0].length;if (matrix == null || rows == 0 || cols == 0) {System.out.println("");}int left = 0;int right = cols - 1;int top = 0;int buttom = rows - 1;int index = 0;int[] result = new int[rows * cols];while (left <= right && top <= buttom) {// 从左到右if (left <= right) {for (int i = left; i <= right; i++) {//System.out.println(matrix[top][i]);result[index++] = matrix[top][i];}}//从上到下if (buttom > top) {for (int i = top + 1; i <= buttom; i++) {//System.out.println(matrix[i][right]);result[index++] = matrix[i][right];}}//从右到左if (right > left && buttom > top) {for (int i = right - 1; i >= left; i--) {//System.out.println(matrix[buttom][i]);result[index++] = matrix[buttom][i];}}//从下到上if (buttom - 1 > top && right > left) {for (int i = buttom - 1; i > top; i--) {//System.out.println(matrix[i][left]);result[index++] = matrix[i][left];}}left++;right--;top++;buttom--;}return result;}
}package DataStructure;public class BinarySearch {public static void main(String[] args) {int[] A = {4,4,10,21};int n = 4;int val = 4;int res = binarySearch(A,n,val);System.out.println(res);}private static int binarySearch(int[] A, int n, int val) {int index = -1;if (n<=0||A==null){return index;}int mid = 0, left = 0, right = n-1;while (left<=right){mid = (left+right)/2;if (A[mid]>val){right = mid-1;}else if (A[mid]<val){left = mid+1;}else { // 找到第一个匹配的值while (mid>=0&&A[mid]==val){mid--;}index = mid+1; //当不满足时跳出循环，因此mid+1break;}}return index;}
}相关问题：LeetCode278：第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例：
给定 n = 5，并且 version = 4 是第一个错误的版本。调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true所以，4 是第一个错误的版本。
答：在二分查找中，选取mid的方法一般为mid=[(left+mid)/2]。如果使用的编程语言有整数溢出的情况（例如C++，Java），那么可以用mid=left+[right-left]/2代替前者。
代码如下：
private static int firstBadVersion(int n){int left = 1;int right = n;while (left<right){int mid = left+(right-left)/2;if (isBadVersion(mid)){right = mid;}else {left = mid+1;}}return left;}
注意，这里更好的写法是int mid = (left+right)>>>1;
补充问题：1） 为什么要left+(right-left)/2（答怕溢出）；2） int 的最大值是？（ 2 31 − 1 = 2147483647 2^{31}-1=2147483647 231−1=2147483647）；3） (right-left)/2会不会出现浮点数？（不会）；4） 二分查找有什么要求，数组有序，升序降序都可以吗？（要求数组/序列满足一定的有序性）；5） 能不能写个代码让升序降序都满足？
答：首先判断数组是否有序：升序或降序，然后根据判断结果执行二分查找。
代码如下：
package DataStructure;public class BinarySearch {public static void main(String[] args) {int val = 4;int n = 9;// 升序int[] A = {1, 2, 4, 4, 9, 10, 15, 17, 21};System.out.println(binarySearch(A, val));// 降序int[] B = {21, 17, 15, 10, 9, 4, 4, 3, 2};System.out.println(binarySearch(B, val));// 无序int[] C = {17, 21, 10, 15, 7, 9, 5, 6, 4};System.out.println(binarySearch(C, val));}/*** 二分查找** @param array :被查找的数组，默认有序* @param val：要查找的数* @return int: 下标位置*/private static int binarySearch(int[] array, int val) {// 1.参数合法性判断if (null == array || array.length == 0) {return -1;}// 2.判断是否有序，以及升序或者降序boolean flag1 = false, flag2 = false;for (int i = 0; i < array.length - 1; i++) {if (array[i] == Math.min(array[i], array[i + 1])) { //升序flag1 = true;} else {flag1 = false;break;}}if (!flag1) {for (int i = 0; i < array.length - 1; i++) {if (array[i] == Math.max(array[i], array[i + 1])) { //降序flag2 = true;} else {flag2 = false;break;}}}if (flag1 || flag2) {return binarySearch(array, array.length, val, flag1);}return -1;}private static int binarySearch(int[] array, int n, int val, boolean up) {int index = -1;int mid = 0, left = 0, right = n - 1;while (left <= right) {mid = left + (right - left) / 2;if (array[mid] > val) {if (up) {right = mid - 1; //升序左移} else {left = mid + 1; //降序右移}} else if (array[mid] < val) {if (up) {left = mid + 1;// 升序右移} else {right = mid - 1; //降序右移}} else { // 找到第一个匹配的值while (mid >= 0 && array[mid] == val) {mid--;}index = mid + 1;break;}}return index;}
}本文发布于:2024-02-02 22:38:50，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170688473046907.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
