Data Structure & Algorithm

💡 Java语言描述

Binary Search 二分查找

• Java基本实现

  public class BinarySearch{
  		public BinarySearch() {
      }
  		// Basic
  		public static int binarySearchBasic(int[] a, int target){
          int i = 0, j = a.length - 1;
          while (i <= j){ //此处包含等号
              int m = (i + j) >>> 1; // 采用无符号右移代替/2得到均值取整
              if (target < a[m]) j = m - 1;
  						else if (a[m] < target) i = m + 1;
              else return m;
          }
          return -1;
      }
  		// Balance
  		public static int binarySearchBalance(int[] a, int target) {
          int i = 0, j = a.length;
          while (1 < j - i) {
              int m = (i + j) >>> 1;
              if (target < a[m]) {
                  j = m;
              } else {
                  i = m;
              }
          } //减少了循环内的平均比较次数
          return (a[i] == target) ? i : -1;
      }
  		// Java inter
  		private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                       long key) {
  		    int low = fromIndex;
  		    int high = toIndex - 1;
  
  		    while (low <= high) {
  		        int mid = (low + high) >>> 1;
  		        long midVal = a[mid];
  
  		        if (midVal < key)
  	            low = mid + 1;
  		        else if (midVal > key)
  	            high = mid - 1;
  		        else
              return mid; // key found
  		    }
  		    return -(low + 1);  // key not found; low为insertIndex
  		}
  }

• 时间复杂度

  • 按时间复杂度从低到高
    • 常量时间 意味着算法时间并不随数据规模而变化
    • 对数时间
    • 线性时间 算法时间与数据规模成正比
    • 拟线性时间
    • 平方时间
    • O 指数时间
    • 阶乘时间
  • 渐进上界asymptotic upper bound：从某个常数开始， 总是位于)上方，那么记作,代表算法执行的最差情况
  • 渐进下界asymptotic lower bound：从某个常数开始， 总是位于)下方，那么记作,代表算法执行的最好情况
  • 渐进紧界asymptotic tight bound：从某个常数开始，总是位于$c_1g(n)c_2g(n)\Theta(g(n))$
  • 二分查找
    • 时间复杂度：最坏：、最好
    • 空间复杂度：常数个指针,额外占用空间是

• **LeftRightmost**

  • 应用

    **

  • code

    • 求排名rank：leftmost(n)+1
    • 求前任predecessor：leftmost(n)-1
    • 求后任successor：rightmost(n)+1
    • 最近邻居

  • 范围查询

    • —> $0 .. leftmost(4) - 1$
    • —> $0 .. rightmost(4)$
    • —> $rightmost(4) + 1 .. \\infty$
    • —> $leftmost(4) .. \\infty$
    • —> $leftmost(4) .. rightmost(7)$
    • —> $rightmost(4)+1 .. leftmost(7)-1$

Array 动态数组

• 插入

  public void add(int index,int element){
      if (index < 0 || index > size) {
          throw new ArrayIndexOutOfBoundsException();
      }
      else if (index >=0 && index < size) {
          System.arraycopy(array, index, array, index + 1, size - index); //索引插入
      }
      array[index] = element; //末端插入
      size++;
  }

• 遍历

  //forEach遍历
  public void foreach(Consumer<Integer> consumer){
      for (int i = 0; i < size; i++) {
          consumer.accept(array[i]);
      }
  }
  //测试
  public void test() {
      DynamicArray dynamicArray = new DynamicArray();
      dynamicArray.addLast(1);
      dynamicArray.addLast(2);
      dynamicArray.addLast(3);
      dynamicArray.addLast(4);
      /*
  		ResultCollector consumer = new ResultCollector();
      dynamicArray.foreach(consumer);
      consumer.test(List.of(1, 2, 3, 4));
  		*/
  		dynamicArray.foreach(e ->{
  		    System.out.println(e);
      });
  }
  //迭代器遍历
  //Stream遍历

• 删除

  public int remove(int index){
      int removed = array[index];
      if (index < 0 || index >= size) {
          throw new ArrayIndexOutOfBoundsException();
      }
      if (index<size-1){
          System.arraycopy(array, index + 1, array, index, size - index - 1);
      }
      size--;
      return removed;
  }

• 扩容

  private void checkAndGrow() {
        if (size==0) {
            array = new int[capacity];
        }else if (size==capacity){
            capacity += capacity >> 1;
            int[] newArray = new int[capacity];
            System.arraycopy(array,0,newArray,0,size);
            array = newArray;
        }
    }

• 局部性原理

  • 缓存的最小存储单位是缓存行cache line，一般是 64 bytes，最少读 64 bytes 填满一个缓存行，因此读入某个数据时也会读取其临近的数据，这就是所谓空间局部性

Linked List 链表