［题目1］：求长度为10000的整型数组的10个最大值。

import java.util.PriorityQueue; public class ArrayTest { private static final int TOTAL = 10; public static void main(String[] args) { int[] array = { 19, 20, 30, 21, 49, 48, 17, 64, 92, 40, 63, 28, 283, 29, 200, 67, 958, 36, 90, 230, 88 }; PriorityQueue<Integer> queue = new PriorityQueue<Integer>(); for (int i = 0; i < TOTAL; i++) { queue.add(Integer.MIN_VALUE); } for (int item : array) { int min = queue.peek(); if (item <= min) { continue; } else { queue.poll(); queue.add(item); } } for (int i = 0; i < TOTAL; i++) { System.out.print(queue.poll() + " "); } } }

运行结果：

63 64 67 88 90 92 200 230 283 958

［题目2］：如何让一个单向链表颠倒顺序。

public class Node { private int value; private Node next; public Node() { } public Node(int value) { this.value = value; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } } import java.util.Stack; public class Link { private int size; private Node head; public Link() { head = new Node(); } public void insert(int value) { Node first = head.getNext(); Node node = new Node(value); node.setNext(first); head.setNext(node); size++; } public Node find(int key) { Node current = head.getNext(); while (current != null) { if (key == current.getValue()) { break; } else { current = current.getNext(); } } return current; } public Node delete(int key) { Node current = head.getNext(); Node prev = head.getNext(); while (current != null) { if (key == current.getValue()) { prev.setNext(current.getNext()); size--; break; } else { prev = current; current = current.getNext(); } } return current; } public Node deleteFirst() { Node first = head.getNext(); if (first != null) { head.setNext(first.getNext()); size--; } return first; } public int size() { return this.size; } public void display() { Node current = head.getNext(); while (current != null) { System.out.print(current.getValue() + " "); current = current.getNext(); } } /** * 移动指针实现倒置 */ public void reverse1() { if (this.size < 2) { return; } Node current = head.getNext(); while (current.getNext() != null) { Node prev = current.getNext(); current.setNext(prev.getNext()); prev.setNext(head.getNext()); head.setNext(prev); } } /** * 借助于栈实现翻转 */ public void reverse2() { Stack<Node> stack = new Stack<Node>(); Node current = head.getNext(); while (current != null) { stack.push(current); current = current.getNext(); } current = stack.pop(); head.setNext(current); for (int i = 0; i < size - 1; i++) { Node next = stack.pop(); current.setNext(next); current = next; } current.setNext(null); } } public class LinkTest { public static void main(String[] args) { Link link = new Link(); link.insert(1); link.insert(2); link.insert(3); link.insert(4); link.insert(5); link.display(); System.out.println(); link.reverse2(); link.display(); } } 运行结果：

5 4 3 2 1 1 2 3 4 5

［题目3］：数组压缩存储

        有这样一道题目，有一个文件，里边有4000000000个正整数，每个数一行，有可能有重复的数，目的查询一个目标值在不在文件中。

        要求：查询时间复杂度尽可能小，最好O(1)。

        首先来分析一下这道题目，如果查询时间复杂度为O(1)，那么只可能把这些数存入数组中，不错，这个想法非常正确，但是让我们来算一算需要多少内存。

        一个int类型的数占4byte，1byte占8bit，所以一个int型的数占用4000000000＊4byte ＝ 16000000000byte ＝ 15625000kb ＝ 15258.8M ＝ 14.9G

        这谁能受得了，所以使用int型数组存储的话需要的内存太大，不能忍受，那么基于这种思路，使用char数组行不行呢，当然可以，一个char占用1byte，相当于使用原来1/4的内存空间，也就是大概3.7G，虽然小了不少，但是还是太大，因为这部分内存会被一直使用着，太浪费了。需要再想一想。

        请看如下这幅图：

        对，没错，就是使用位存储，把原来32个下标对应到一个int型数的32个位上边，然后再把这个整数对应到一个新的数组的下标上，相当于把原来的int型数组压缩为原来的1/32，那么这么算起来所占用的内存空间变为：4000000000＊4byte/32 = 500000000byte = 488281k = 476.8M， 这个内存占用空间是可以接受的。

        OK，思路分析完了，下面来看代码：

package test.array; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.FileWriter; public class BigArrayStorage { private static final String PATH = "file/int.txt"; private static final long LINE = 4000000000l; private static int[] array = new int[(int) (1 + LINE / 32)]; private static File FILE = new File(PATH); public static void main(String[] args) { long startInit = System.currentTimeMillis(); initFile(); long endInit = System.currentTimeMillis(); System.out.print("初始化需要的时间： "); System.out.println(endInit - startInit); // long startStore = System.currentTimeMillis(); // storeArray(); // long endStore = System.currentTimeMillis(); // System.out.print("存储需要的时间： "); // System.out.println(endStore - startStore); // // long startSearch = System.currentTimeMillis(); // System.out.print("查询到1999999994： "); // System.out.println(search(1999999994)); // long end1 = System.currentTimeMillis(); // System.out.print("查询1999999994所需要的时间： "); // System.out.println(end1 - startSearch); // // System.out.println("查询到2000000001： "); // System.out.println(search(2000000001)); // long end2 = System.currentTimeMillis(); // System.out.print("查询2000000001所需要的时间： "); // System.out.println(end2 - end1); } /** * 初始化文件，模拟4000000000个数字 */ public static void initFile() { try { FileWriter fileWriter = new FileWriter(FILE); for (long i = 0; i < LINE / 2; i++) { fileWriter.write(i + 1 + "\n"); } for (long i = 0; i < LINE / 2; i++) { fileWriter.write(i + 1 + "\n"); } fileWriter.close(); } catch (Exception e) { e.printStackTrace(); } } /** * 把4000000000个数字转换存入数组中，这里采用按位存储，所以int型可以存32个下标，一个下标对应一位， 这就是压缩存储，因为设计的目的是只需要知道这个数字有没有在文件中出现 */ public static void storeArray() { try { FileReader fileReader = new FileReader(FILE); BufferedReader reader = new BufferedReader(fileReader); String value = null; while ((value = reader.readLine()) != null) { int intValue = Integer.parseInt(value); // 求在数组中的下标 int index = intValue / 32; // 求在32位中，使用哪一位来存储当前下标值 int position = intValue % 32; // 1左移position位是把第position位置为1，其它位为0 // “｜”上当前数组值是不改变其它下标对应的值 array[index] = array[index] | (1 << position); } reader.close(); fileReader.close(); } catch (Exception e) { e.printStackTrace(); } } /** * 查询目标值是否在数组中 * * @param target * 目标值 * @return true 查到， false 查不到 */ public static boolean search(int target) { // 求在数组中的下标 int index = target / 32; // 求在32位中，使用哪一位来存储当前下标值 int position = target % 32; int value = array[index]; // 当前值“&”上1左移position是为了获取第position为的值，此时把其它位都置为0了 value = value & (1 << position); // 无符号右移position位是为了把最后以为置为1，取得其十进制数判断是0或1 value = value >>> position; if (value == 1) { return true; } else { return false; } } }

初始化数组需要时间： 586396         然后修改一下main函数：

public static void main(String[] args) { // long startInit = System.currentTimeMillis(); // initFile(); // long endInit = System.currentTimeMillis(); // System.out.print("初始化需要的时间： "); // System.out.println(endInit - startInit); long startStore = System.currentTimeMillis(); storeArray(); long endStore = System.currentTimeMillis(); System.out.print("存储需要的时间： "); System.out.println(endStore - startStore); long startSearch = System.currentTimeMillis(); System.out.print("查询到1999999994： "); System.out.println(search(1999999994)); long end1 = System.currentTimeMillis(); System.out.print("查询1999999994所需要的时间： "); System.out.println(end1 - startSearch); System.out.print("查询到2000000001： "); System.out.println(search(2000000001)); long end2 = System.currentTimeMillis(); System.out.print("查询2000000001所需要的时间： "); System.out.println(end2 - end1); }

存储需要的时间： 289248 查询到1999999994： true 查询1999999994所需要的时间： 1 查询到2000000001： false 查询2000000001所需要的时间： 0         在内存中的数组，查询效率非常快，只需要O(1)的时间。内存占用也非常的少。到此，这个问题完美解决。