跳至主要內容

数组

HeChuangJun约 4360 字大约 15 分钟

数组

  • 数组是存放在连续内存空间上的相同类型数据的集合

  • 数组通过下标访问数据，从0开始

  • 数组内的元素是连续存储的，数组中元素的地址由公式 BaseAddress+i∗size 计算出索引 i 元素的地址, BaseAddress数组的数据起始地址，i 即索引.size 是每个元素占用字节

  • 动态数组的大小可以增大或缩小。

  • 二维数组 Array[m][n] m 是外层数组的长度（row 行） n 是内层数组的长度（column 列）当访问 Array[i][j]，0≤i<m,0≤j<n时，就相当于先找到第 i 个内层数组（行）再找到此内层数组中第 j 个元素（列）

  • 使用场景

    • 存储和访问顺序数据
    • 临时存储对象
    • IO缓冲区
    • 查找表和逆查找表
    • 从函数返回多个值
    • 动态规划以缓存子问题的答案

  • 复杂度

静态数组动态数组
访问O(1)O(1)
搜索O(n)O(n)
插入(头中)N/AO(n)
插尾部N/AO(1)
删除N/AO(n)
  • 访问时间恒定O(1)，因为数组是可索引的，
  • 搜索需要线性时间O(n)最坏需要遍历整个数组，
  • 假如你查找的元素不存在然后插入，或者追加、删除数据没有意义，因为静态数组是固定大小的，动态数组会增加成本，插入、删除元素都可能需要移动元素并新建数组移动元素然后把原数组元素复制过去,所以插入删除都是O(n)，
  • 对于追加由于需要扩容再复制操作情况较少发生因此是O(1)

泛型动态数组实现

@SuppressWarnings("unchecked")
public class DynamicArray<T> implements Iterable<T> {

  private T[] arr;
  private int len = 0; // length user thinks array is
  private int capacity = 0; // Actual array size

  public DynamicArray() {
    this(16);
  }

  public DynamicArray(int capacity) {
    if (capacity < 0) throw new IllegalArgumentException("Illegal Capacity: " + capacity);
    this.capacity = capacity;
    arr = (T[]) new Object[capacity];
  }

  public int size() { return len; }

  public boolean isEmpty() { return size() == 0; }

  public T get(int index) { return arr[index]; }

  public void set(int index, T elem) { arr[index] = elem; }

  public void clear() { for (int i = 0; i < len; i++) arr[i] = null; len = 0; }

  public void add(T elem) {
    // Time to resize!
    if (len + 1 >= capacity) {
      if (capacity == 0) capacity = 1;
      else capacity *= 2; // double the size
      T[] new_arr = (T[]) new Object[capacity];
      for (int i = 0; i < len; i++) new_arr[i] = arr[i];
      arr = new_arr; // arr has extra nulls padded
    }

    arr[len++] = elem;
  }

  // Removes an element at the specified index in this array.
  public T removeAt(int rm_index) {
    if (rm_index >= len || rm_index < 0) throw new IndexOutOfBoundsException();
    T data = arr[rm_index];
    T[] new_arr = (T[]) new Object[len - 1];
    for (int i = 0, j = 0; i < len; i++, j++)
      if (i == rm_index) j--; // Skip over rm_index by fixing j temporarily
      else new_arr[j] = arr[i];
    arr = new_arr;
    capacity = --len;
    return data;
  }

  public boolean remove(Object obj) {
    int index = indexOf(obj);
    if (index == -1) return false;
    removeAt(index);
    return true;
  }

  public int indexOf(Object obj) {
    for (int i = 0; i < len; i++) {
      if (obj == null) {
        if (arr[i] == null) return i;
      } else {
        if (obj.equals(arr[i])) return i;
      }
    }
    return -1;
  }

  public boolean contains(Object obj) { return indexOf(obj) != -1;}

  // Iterator is still fast but not as fast as iterative for loop
  @Override
  public java.util.Iterator<T> iterator() {
    return new java.util.Iterator<T>() {
      int index = 0;
      @Override
      public boolean hasNext() { return index < len; }

      @Override
      public T next() { return arr[index++]; }

      @Override
      public void remove() { throw new UnsupportedOperationException(); }
    };
  }

  @Override
  public String toString() {
    if (len == 0) return "[]";
    else {
      StringBuilder sb = new StringBuilder(len).append("[");
      for (int i = 0; i < len - 1; i++) sb.append(arr[i] + ", ");
      return sb.append(arr[len - 1] + "]").toString();
    }
  }
}

88合并有序数组√

  • 将数组内两个区间内的有序元素合并，例[1, 5, 6, 2, 4, 10, 11]可以视作两个有序区间[1, 5, 6] 和 [2, 4, 10, 11]合并后，结果仍存储于原有空间[1, 2, 4, 5, 6, 10, 11]
时间复杂度O(n)空间复杂度O(n)a2
public static int[] mergeSortedArrays(int[] arr1, int[] arr2) {
    int n1 = arr1.length;
    int n2 = arr2.length;
    int[] mergedArray = new int[n1 + n2];
    int i = 0, j = 0, k = 0;
    // 遍历两个数组并将较小的元素放入 mergedArray
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            mergedArray[k++] = arr1[i++];
        } else {
            mergedArray[k++] = arr2[j++];
        }
    }

    // 如果 arr1 还有剩余的元素
    while (i < n1) {
        mergedArray[k++] = arr1[i++];
    }

    // 如果 arr2 还有剩余的元素
    while (j < n2) {
        mergedArray[k++] = arr2[j++];
    }

    return mergedArray;
}

t189轮转/翻转数组√

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

数组翻转
将所有元素翻转，这样尾部的 kmodn 个元素就被移至数组头部，
然后再翻转 [0,kmodn−1] 区间的元素和 [kmodn,n−1] 区间的元素即能得到答案

以 n=7，k=3 为例：
原始数组	1 2 3 4 5 6 7
翻转所有元素	7 6 5 4 3 2 1
翻转 [0,kmodn−1] 区间的元素	5 6 7 4 3 2 1
翻转 [kmodn,n−1] 区间的元素	5 6 7 1 2 3 4
时间复杂度：O(n)，每个元素被翻转两次，共n个元素，总时间复杂度为O(2n)=O(n)
空间复杂度：O(1)。
class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    //start、end都是索引
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}

t53最大子序和

  • 整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
  • 例如输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
思路：动态规划
设f(n)为以第n个数作为结尾的连续子数组和，那么f(n)只能是来源于f(n-1)+n或者n，其中f(0)=nums[0]
时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
空间复杂度：O(1)。我们只需要常数空间存放若干变量。
public int maxSubArray(int[] nums) {
    int pre = 0, maxAns = nums[0];
    for (int x : nums) {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    }
    return maxAns;
}

t56合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

思路：
所有数组按照左端点从小到大排序，将左端点小于右端点的合并
时间复杂度：O(nlogn)。除去排序的开销，我们只需要一次线性扫描
空间复杂度：O(logn)。存储答案之外使用的额外空间
public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) {
        return new int[0][2];
    }
    Arrays.sort(intervals, new Comparator<int[]>() {
        public int compare(int[] interval1, int[] interval2) {
            return interval1[0] - interval2[0];
        }
    });
    List<int[]> merged = new ArrayList<int[]>();
    for (int i = 0; i < intervals.length; ++i) {
        int L = intervals[i][0], R = intervals[i][1];
        //最后一个数组范围最右与当前数组范围不重合
        if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
          merged.add(new int[]{L, R});
        } else {
          //重合则选出最大的右并更新最后一个数组范围的右
          merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
        }
    }
    return merged.toArray(new int[merged.size()][]);
}

t238除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:输入: nums = [1,2,3,4] 输出: [24,12,8,6]

思路：左边数组累计乘积x右边数组累计乘积=answer
时间复杂度：O(N)，其中 N 指的是数组 nums 的大小。分析与方法一相同。
空间复杂度：O(1)，输出数组不算进空间复杂度中，因此我们只需要常数的空间存放变量。
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length];

        // answer[i] 表示索引 i 左侧所有元素的乘积
        // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
        answer[0] = 1;
        //[1,2,3,4]=>answer[1,1,2,6]
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }

        // R 为右侧所有元素的乘积
        // 刚开始右边没有元素，所以 R = 1
        int R = 1;
        //[1,2,3,4]=>R1->4->12->24=>answer[24,12,8,6]
        for (int i = length - 1; i >= 0; i--) {
            // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
            answer[i] = answer[i] * R;
            // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
            R *= nums[i];
        }
        return answer;
    }
}

t41缺失的第一个正数

未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：输入：nums = [1,2,0]输出：3
解释：范围 [1,2] 中的数字都在数组中。

思路：将n放到nums[n-1]中，nums[nums[i] - 1] != nums[i]避免重复交换
时间复杂度：O(N)，其中 N 是数组的长度。
空间复杂度：O(1)。
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

27移除元素√

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
  public int removeElement(int[] nums, int val) {
      // 快指针遍历元素，慢指针表示不为目标元素的值
      int slowIndex = 0;
      for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
          if (nums[fastIndex] != val) {
              nums[slowIndex] = nums[fastIndex];
              slowIndex++;
          }
      }
      return slowIndex;
  }
}

977有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

class Solution {
    public int[] sortedSquares(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        int[] result = new int[nums.length];
        int index = result.length - 1;//从逆序开始防止更负的反而更大
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                // 正数的相对位置是不变的， 需要调整的是负数平方后的相对位置
                result[index--] = nums[left] * nums[left];
                ++left;
            } else {
                result[index--] = nums[right] * nums[right];
                --right;
            }
        }
        return result;
    }
}

209长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

class Solution {
    // 滑动窗口
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

58区间和

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

前缀和:思想是重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数。
求 区间下标 [2, 5] 的区间和，那么应该是 p[5] - p[1]，而不是 p[5] - p[2]
public class Main {
    //第一行输入为整数数组 Array 的长度 n，
    //接下来 n 行，每行一个整数，表示数组的元素。
    //随后的输入为需要计算总和的区间，直至文件结束。  
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] vec = new int[n];
        int[] p = new int[n];

        int presum = 0;
        for (int i = 0; i < n; i++) {
            vec[i] = scanner.nextInt();
            presum += vec[i];
            p[i] = presum;
        }

        while (scanner.hasNextInt()) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            int sum;
            if (a == 0) {
                sum = p[b];
            } else {
                sum = p[b] - p[a - 1];
            }
            System.out.println(sum);
        }

        scanner.close();
    }
}

44开发商购买土地

在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。
注意：区块不可再分。

如果将区域按照如下方式划分：
1 2 | 3 2 1 | 3 1 2 | 3
两个子区域内土地总价值之间的最小差距可以达到 0。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //第一行输入两个正整数，代表 n 和 m。 
        //接下来的 n 行，每行输出 m 个正整数。
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int sum = 0;
        int[][] vec = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                vec[i][j] = scanner.nextInt();
                sum += vec[i][j];
            }
        }

        // 统计横向
        int[] horizontal = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                horizontal[i] += vec[i][j];
            }
        }

        // 统计纵向
        int[] vertical = new int[m];
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                vertical[j] += vec[i][j];
            }
        }

        int result = Integer.MAX_VALUE;
        int horizontalCut = 0;
        for (int i = 0; i < n; i++) {
            horizontalCut += horizontal[i];
            //horizontalCut 是当前切割点上方部分的元素和，
            //sum - 2 * horizontalCut 计算的是上下两部分的元素和差值。
            //result 保存所有可能的切割差值中的最小值。
            result = Math.min(result, Math.abs(sum - 2 * horizontalCut));
        }

        int verticalCut = 0;
        for (int j = 0; j < m; j++) {
            verticalCut += vertical[j];
            result = Math.min(result, Math.abs(sum - 2 * verticalCut));
        }

        System.out.println(result);
        scanner.close();
    }
}

稀疏数组sparsearray

  • 稀疏数组：当保存一个数组中大部分元素为0或者同一个值的时，节省存储空间，如果写入磁盘则减少I/O，提升性能
  • 问题:五子棋程序存盘退出和续上盘功能，二维数组的棋盘、地图等
  • 思路:
    • 二维数组 -> 稀疏数组
      • 遍历二维数组得到有效数据的个数sum
      • 根据sum 创建稀疏数组sparseArr int[sum + 1][3](留个一维数组数组一共有几行几列，有多少个不同的值)
      • 第1个一维数组记录数组的一维数组个数、二维数组的个数、有效数据个数sum
      • 从第2个一维数组开始记录数组的有效数据（int[?][1]和int[?][2]记录有效数据的位置int[?][3]记录有效数据的值）直到所有数组记录完
    • 稀疏数组 转 二维数组思路
      • 先根据读取稀疏数组的第一个一维数组数据建立二维数组
      • 从第2个一维数组开始将给二维数组一一赋值
稀疏数组2.png
稀疏数组2.png
public class SparseArray {
    public static void main(String[] args) {
        int[][] testarray = new int[5][6];
        testarray[2][1] = 3;
        testarray[0][3] = 10;
        testarray[4][5] = 4;
        System.out.println("原来数组~~");
        printArray(testarray);
        System.out.println("稀疏数组~~");
        printArray(getSpaseArray(testarray));
        System.out.println("原来数组~~");
        printArray(getOldArray(getSpaseArray(testarray)));
    }
    
    public static int[][] getSpaseArray(int[][] oldArray){
        //1.求出有效数据的个数
        int sum = 0;
        for(int i=0;i<oldArray.length;i++){
            for(int j=0;j<oldArray[i].length;j++){
                if(oldArray[i][j]!=0){
                    sum++;
                }
            }
        }
        //2.创建稀疏数组
        int[][] result= new int[sum+1][3];
        result[0][0] = oldArray.length;//每个赋值
        result[0][1] = oldArray[0].length;
        result[0][2] = sum;
        int index = 0;//用于记录是第几个非0数据,稀疏数组的"第几行"
        for(int i=0;i<oldArray.length;i++){
            for(int j=0;j<oldArray[i].length;j++){
                if(oldArray[i][j]!=0){
                    index++;
                    result[index][0] = i;
                    result[index][1] = j;
                    result[index][2] = oldArray[i][j];
                }
            }
        }
        return result;
    }
    
    public static int[][] getOldArray(int[][] spaseArray){
        int[][] result = new int[spaseArray[0][0]][spaseArray[0][1]];
        for(int i=1;i<spaseArray.length;i++){//将后面几行读取完就行了
            result[spaseArray[i][0]][spaseArray[i][1]] = spaseArray[i][2];
        }
        return result;
    }
    
    public static void printArray(int[][] printarray){
        for(int i=0;i<printarray.length;i++){
            for(int j=0;j<printarray[i].length;j++){
                System.out.printf("%d\t",printarray[i][j]);
            }
            System.out.println();
        }
    }
}