之所以在归并排序中增加这个硬盘操作，是因为我做这道题想起来很久之前遇到的一道面试题。就是问如何用1G的空间，去排序8G的数据。答案就是采用归并排序（当时原理说出来了，但是白板没写好）。
package tech.jarry.learning.test.algorithms.mergesort; import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** * 模仿真实硬盘，进行数据的存储与打印数据 */ public class Disk { private static List<Integer> diskIntegerInstance = new ArrayList<>(); public static void store(int element) { diskIntegerInstance.add(element); } public static void printAll() { Iterator<Integer> integerIterator = diskIntegerInstance.iterator(); while (integerIterator.hasNext()) { System.out.println(integerIterator.next()); } } } 算法测试 package tech.jarry.learning.test.algorithms.mergesort; import java.util.Arrays; public class MergeSortTest { public static void main(String[] args) { int[] testArray = new int[] {3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12}; // 3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12 // correct result: [0, 1, 2, 3, 4, 5, 5, 7, 9, 12, 18] int[] resultArray = MergeSort.mergeSort(testArray); System.out.println(Arrays.toString(resultArray)); } }结果输出
[0, 1, 2, 3, 4, 5, 5, 7, 9, 12, 18] 确定两数之和为固定值这道题在leetcode中是存在的，之前的博客也有对应的解析。甚至leetcode还有求三数之和为确定值的题目。
算法实现 package tech.jarry.learning.ch2.algorithms.twosum; import tech.jarry.learning.ch2.algorithms.mergesort.MergeSort; public class TwoSum { // 题目中只要求实现确定是否存在，而无需返回对应index。否则，需要注意剔除相同index的问题，并修改binarySearch的返回值 public static boolean twoSum(int[] array, int target) { array = MergeSort.mergeSort(array); for (int i = 0; i < array.length; i++) { int branchTarget = target - array[i]; // 二分查找的时间复杂度为lgn if (binarySearch(array, branchTarget)) { return true; } } return false; } private static boolean binarySearch(int[] array, int target) { return binarySearch(array, target, 0, array.length - 1); } private static boolean binarySearch(int[] array, int target, int startIndex, int endIndex) { if (endIndex > startIndex) { int middleIndex = (endIndex + startIndex) / 2; if (target < array[middleIndex]) { return binarySearch(array, target, startIndex, middleIndex); } else if (target > array[middleIndex]) { return binarySearch(array, target, middleIndex + 1, endIndex); } else if (target == array[middleIndex]) { return true; } } return false; } } 算法测试 package tech.jarry.learning.test.algorithms.twosum; public class TwoSumTest { public static void main(String[] args) { int[] testArray = new int[] {3, 5, 7, 2, 4, 1, 5, 0, 9, 18 ,12}; int target = 80; System.out.println(TwoSum.twoSum(testArray, target)); } }结果输出
false