数据结构和算法-数组

发表于 更新于 分类于 Disqus：
数组概述以及数组相关题解思路和技巧

概述

数组是内存中连续的区域，可以通过下标去访问。

时间复杂度

  • 查询的时间复杂度为O(1)
  • 插入和删除平均复杂度为O(n)

Java本地函数库

java.lang.Math

java.util.Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 排序
public static void sort(int[] a);
public static void sort(int[] a, int fromIndex, int toIndex);//左开右闭
// 加入比较器排序
public static <T> void sort(T[] a, Comparator<? super T> c);
public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c);
// 二分查找
public static int binarySearch(int[] a, int key);
public static int binarySearch(int[] a, int fromIndex, int toIndex, int key)；//左开右闭
// 填充数组  
public static void fill(int[] a, int val);
public static void fill(int[] a, int fromIndex, int toIndex, int val);//左开右闭
// 数组复制
public static int[] copyOf(int[] original, int newLength);
public static int[] copyOfRange(int[] original, int from, int to);//左开右闭

算法

基础数组算法

找出数组中最大元素

1
2
3
4
5
6
7
8
9
10
11
12
public static int getMaxNum(int[] nums) {
  if (nums.length < 2) {
    return -1;
  }
  int maxNum = nums[0];
  for (int i = 1; i < nums.length; i++) {
    if (nums[i] > maxNum) {
      maxNum = nums[i];
    }
  }
  return maxNum;
}

计算数组的平均值

1
2
3
4
5
6
7
8
9
10
public static int getAverageNum(int[] nums) {
  if (nums.length < 2) {
    return -1;
  }
  int sum = 0;
  for (int num : nums) {
    sum += num;
  }
  return sum / nums.length;
}

复制数组

1
2
3
4
5
public static int[] copyArray(int[] nums) {
  int[] newArray = new int[nums.length];
  System.arraycopy(nums, 0, newArray, 0, nums.length);
  return newArray;
}

颠倒数组元素的顺序

1
2
3
4
5
6
7
8
9
10
11
public static void reverseArray(int[] nums) {
  if (nums.length < 1) {
    return;
  }
  int N = nums.length;
  for (int i = 0; i < N/2; i++) {
    int temp = nums[i];
    nums[i] = nums[N - 1 - i];
    nums[N - 1 -i] = temp;
  }
}

判断一个数是否是素数

1
2
3
4
5
6
public static boolean isPrime(int num) {
  if (num < 2) return false;
  for (int i = 2; i*i <= num; i++)
    if (num % i == 0) return false;
  return true;
}

排序

不借助其他空间，数组本身进行排序。

冒泡排序

思路

每次遍历都找出一个最大或最小值，放在数组的末尾，然后对剩下的数组元素继续遍历，寻找次大值或次小值。

解法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void bubbleSort(int[] nums) {
  if (nums.length < 1) {
    return;
  }
  for (int i = 0; i < nums.length; i++) {
    for (int j = 0; j < nums.length - 1 - i; j++) {
      if (nums[j + 1] > nums[j]) {
        int temp = nums[j + 1];
        nums[j + 1] = nums[j];
        nums[j] = temp;
      }
    }
  }
}

第二次遍历时，要限制次数为 nums.length - 1 - i，i代表的含义是有i个元素已经排好序了，- 1有两个含义，一个是防止下标越界，另外是遍历到最后一个元素时不需要进行比较了。

解法二

假设我们现在排序ar[]={1,2,3,4,5,6,7,8,10,9}这组数据，按照上面的排序方式，第一趟排序后将10和9交换已经有序，接下来的8趟排序就是多余的，什么也没做。所以我们可以在交换的地方加一个标记，如果那一趟排序没有交换元素，说明这组数据已经有序，不用再继续下去。

思路：当出现一次元素不交换时，代表着数组已经排序好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void bubbleSort2(int[] nums) {
  if(nums.length < 2) return;
  int flag = 1;
  for (int i = 0; i < nums.length; i++) {
    for (int j = 0; j < nums.length - i - 1; j++) {
      if (nums[j + 1] > nums[j]) {
        int temp = nums[j + 1];
        nums[j + 1] = nums[j];
        nums[j] = temp;
        flag = 0;
      }
    }
    if (flag == 1) {
      return;
    }
  }
}
解法三

上面优化仅仅适用于连续有序而整体无序的数据(例如：1， 2，3 ，4 ，7，6，5)。
但是对于前面大部分是无序而后边小半部分有序的数据(1，2，5，7，4，3，6，8，9，10)排序效率也不可观，对于种类型数据，我们可以继续优化。既我们可以记下最后一次交换的位置，后边没有交换，则后面必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void bubbleSort3(int[] nums) {
  if(nums.length < 1) return;
  int k = nums.length - 1;
  int pos;

  for (int i = 0; i < nums.length; i++) {
    pos = 0;
    for (int j = 0; j < k; j++) {
      if (nums[j + 1] > nums[j]) {
        int temp = nums[j + 1];
        nums[j + 1] = nums[j];
        nums[j] = temp;
        pos = j;
      }
    }
    k = pos;
  }
}
复杂度分析

可以看到不论做何种优化，因为2层loops，所以平均时间复杂度为：O(n^2)。

选择排序

思路

首先，找到数组中最小的那个元素，其次，将它和数组的第 一个元素交换位置。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void selectionSort(int[] nums) {
  if(nums.length < 2) return;
  for (int i = 0; i < nums.length; i++) {
    int minIndex = i;
    for (int j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex != i) {
      int temp = nums[i];
      nums[i] = nums[minIndex];
      nums[minIndex] = temp;
    }
  }
}

可以看到，和冒泡排序在思路上有一些区别，冒泡排序是数组尾端是有序的，而选择排序数组头部是有序的，和优化后的冒泡排序类似。

为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。 这种性质在某些情况下是缺点，因为使用选择排序的人可能会惊讶地发现，一个已经有序的数组或 是主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长。

复杂度分析

可以看到，还是2层循环，平均复杂度为：O(n^2)。

插入排序

思路

构建有序序列，对于未排序数据，在已排好序的序列中从后向前扫描，找到相应位置并插入。通常人们整理扑克的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。

算法描述
  • 从第一个元素开始，该元素认为是已排序；
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  • 在已经排序的元素序列中找到合适的位置。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
public static void insertSort(int[] nums) {
  if(nums.length < 2) return;
  for (int i = 0; i < nums.length - 1; i++) {
    int current = nums[i + 1];
    int preIndex = i;
    while (preIndex >= 0 && current < nums[preIndex]) {
      nums[preIndex + 1] = nums[preIndex];
      preIndex--;
    }
    nums[preIndex + 1] = current;
  }
}

和选择排序不同，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大 且其中的元素已经有序(或接近有序)的数组进行排序将会比对随机顺序的数组或是逆序数组进行 排序要快得多。

复杂度分析

可以看到时间复杂度也是：O(n^2)；

快排

思路

通过一趟排序将待排序的记录分为两部分，其中一部分记录的关键字均比另一部分小，然后对这两部分继续进行排序，以达到整个数组有序。

算法描述
  • 设置两个变量i、j，排序开始的时候：i=0，j=N-1；
  • 以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
  • 从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；
  • 从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
  • 重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int[] qsort(int arr[],int start,int end) {
  int pivot = arr[start];
  int i = start;
  int j = end;
  while (i<j) {
    while ((i<j)&&(arr[j]>pivot)) {
      j--;
    }
    while ((i<j)&&(arr[i]<pivot)) {
      i++;
    }
    if ((arr[i]==arr[j])&&(i<j)) {
      i++;
    } else {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
  if (i-1>start) arr=qsort(arr,start,i-1);
  if (j+1<end) arr=qsort(arr,j+1,end);
  return (arr);
}
复杂度分析

快速排序的平均时间复杂度也是O(nlog2n)。

Leetcode

No251.找出数组第k大元素

解法一
1
2
3
4
5
public int findKthLargest(int[] nums, int k) {
        final int N = nums.length;
        Arrays.sort(nums);
        return nums[N - k];
}

复杂度分析：

时间复杂度：O(NlgN) ，空间复杂度：O(1)。

解法二
1
2
3
4
5
6
7
8
9
10
11
12
public int findKthLargest(int[] nums, int k) {

    final PriorityQueue<Integer> pq = new PriorityQueue<>();
    for(int val : nums) {
        pq.offer(val);

        if(pq.size() > k) {
            pq.poll();
        }
    }
    return pq.peek();
}

对于整形数组来说，优先级队列的peek()和poll()返回的的队首的元素，是整个队列中最小的元素。

复杂度分析：

时间复杂度：O(NlgN) ，空间复杂度：O(K)。

0%