数据结构面试题：数组

使用二重循环两两比较得到重复元素，时间复杂度为 O(n^2) 。

for (int i = 0; i < names.length; i++) {
    for (int j = i + 1 ; j < names.length; j++) {
        if (names[i].equals(names[j])) {
            // 得到重复元素
使用Set，因为Set不允许插入重复元素，可通过add()的返回值判断元素是否重复，时间复杂度为 O(n)。
for (String name : names) {
    if (set.add(name) == false) {
        // 得到重复元素
使用哈希表，遍历数组元素通过数组元素值与元素数量构建哈希表，再遍历哈希表输出数量非1的元素即为重复元素。这种方法时间复杂度为 O(n)，与方法二相同，但却能够准确求到重复数量。
// 构造哈希表
for (String name : names) {
    Integer count = nameAndCount.get(name);
    if (count == null) {
        nameAndCount.put(name, 1);
    } else {
        nameAndCount.put(name, ++count);
// 打印重复元素以及重复数量
Set<Entry<String, Integer>> entrySet = nameAndCount.entrySet();
for (Entry<String, Integer> entry : entrySet) {
    if (entry.getValue() > 1) {
        System.out.printf("duplicate element '%s' and count '%d' :", entry.getKey(), entry.getValue());
6. 用Java从一个给定数组中删除重复元素

不借助数据结构，申请一个跟给定数组一样大小的新数组，遍历给定数组将给定数组中的每一个元素放入新数组中，放入时遍历新数组判断是否已存在，时间复杂度为 O(n^2)。
使用List的contains，本质上跟方法一一样。
int[] attr = { 1, 2, 3, 3, 5, 5, 7, 9 };
List<Integer> list = new ArrayList<Integer>();
for (int i : attr) {
    if (!list.contains(i)) {
        list.add(i);
使用Set或LinkedHashSet，特别是LinkedHashSet，因为它能够保持元素是有序的，时间复杂度为 O(n)。
先排序再遍历放入新数组中，可根据数组有序的特性快速过滤掉重复元素，时间复杂度由排序算法决定。
7. 如何利用快速排序对一个整型数组进行排序

快速排序过程如下。
public class QuickSortDemo{
    public static void main(String args[]) {
        // unsorted integer array
        int[] unsorted = {6, 5, 3, 1, 8, 7, 2, 4};
        System.out.println("Unsorted array :" + Arrays.toString(unsorted));
        QuickSort algorithm = new QuickSort();
        // sorting integer array using quicksort algorithm
        algorithm.sort(unsorted);
        // printing sorted array
        System.out.println("Sorted array :" + Arrays.toString(unsorted));
class QuickSort {
    private int input[];
    private int length;
    public void sort(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return;
        this.input = numbers;
        length = numbers.length;
        quickSort(0, length - 1);
     * This method implements in-place quicksort algorithm recursively.
    private void quickSort(int low, int high) {
        int i = low;
        int j = high;
        // pivot is middle index
        int pivot = input[low + (high - low) / 2];
        // Divide into two arrays
        while (i <= j) {
             * As shown in above image, In each iteration, we will identify a
             * number from left side which is greater then the pivot value, and
             * a number from right side which is less then the pivot value. Once
             * search is complete, we can swap both numbers.
            while (input[i] < pivot) {
                i++;
            while (input[j] > pivot) {
                j--;
            if (i <= j) {
                swap(i, j);
                // move index to next position on both sides
                i++;
                j--;
        // calls quickSort() method recursively
        if (low < j) {
            quickSort(low, j);
        if (i < high) {
            quickSort(i, high);
    private void swap(int i, int j) {
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
Output :
Unsorted array :[6, 5, 3, 1, 8, 7, 2, 4]
Sorted array :[1, 2, 3, 4, 5, 6, 7, 8]
8. 用 Java 实现数组反转

数组第一个元素与最后一个元素交换，第二个元素与倒数第二个元素交换，时间复杂度为 O(n/2)或O(n)，空间复杂度O(1)。