8_数据结构设计.md

数据结构设计

*1、设计哈希集合（705）

705. 设计哈希集合

//思路一：使用动态数组作为底层数据数据结构
//扩容 size == 数组长度 扩容为原来的 2 倍
//缩容 size == 数组长度/4 缩容为原的 1/2 
class MyHashSet {
  private int size; // 该 set 的长度
  private int capacity=10; //该 set 的初始容量，默认是10
  private int[] data; //使用 int 数组作为 set 的底层数据结构

  /** Initialize your data structure here. */
  public MyHashSet() {
    size = 0;
    data = new int[capacity];
  }

  //添加元素
  //先判断元素是否存在:
  //若存在，则不用操作
  //若不存在，则先判断是否超过数组容量，再添加元素
  public void add(int key) {
    if(find(key)!=-1){
      return;
    }
    if(size==data.length){
      resize(2*data.length);
    }
    data[size++] = key;
  }

  //删除元素
  //先判断元素是否存在:
  //若存在，则先进行删除，再将 size--，然后再调整数组容量
  //若不存在，则不用操作
  public void remove(int key) {
    if(find(key)==-1){
      return;
    }
    int index = find(key);
    for(int i=index;i<size-1;i++){
      data[i] = data[i+1];
    }
    size--;
    if(size==data.length/4 && data.length/2!=0){
      resize(data.length/2);
    }
  }

  /** Returns true if this set contains the specified element */
  public boolean contains(int key) {
    if(find(key)==-1){
      return false;
    }
    return true;
  }

  //根据 key 查看元素
  //若找到，回复元素下标
  //若找不到，返回 -1
  private int find(int key){
    for(int i=0;i<size;i++){
      if(data[i]==key){
        return i;
      }
    }
    return -1;
  }

  //重新调整底层数组的容量
  private void resize(int newCapacity){
    int[] newData = new int[newCapacity];
    for(int i=0;i<size;i++){
      newData[i] = data[i];
    }
    data = newData;
  }
}

@Test
public void test(){
  MyHashSet set = new MyHashSet();
  set.add(1);
  set.add(1);
  set.add(2);
  set.add(3);
  set.add(4);
  set.add(5);
  set.remove(5);
  System.out.println(set.contains(1));
  System.out.println(set.contains(5));
}

//思路二：以空间换时间
//所有的值都在 [1, 1000000]的范围内 --> 可以建立一个长度为 1000001数组
class MyHashSet {
  private int[] data;

  /** Initialize your data structure here. */
  public MyHashSet() {
    data = new int[1000001];
  }

  public void add(int key) {
    if(contains(key)){
      return;
    }
    data[key]=1;
  }

  public void remove(int key) {
    if(!contains(key)){
      return;
    }
    data[key] = 0;
  }

  /** Returns true if this set contains the specified element */
  public boolean contains(int key) {
    if(data[key]>0){
      return true;
    }
    return false;
  }
}

@Test
public void test(){
  MyHashSet set = new MyHashSet();
  set.add(1);
  set.add(1);
  set.add(2);
  set.add(3);
  set.add(4);
  set.add(5);
  set.remove(5);
  System.out.println(set.contains(1));
  System.out.println(set.contains(5));
}

*2、设计哈希映射（706）

706. 设计哈希映射

//思路：与 705 题类似，以空间换时间，但是要注意 value 的取值
class MyHashMap {
  private int[] data;

  /** Initialize your data structure here. */
  public MyHashMap() {
    data = new int[1000001];
    for(int i=0;i<1000001;i++){
      data[i]=-1;
    }
  }

  /** value will always be non-negative. */
  public void put(int key, int value) {
    data[key] = value;
  }

  /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
  public int get(int key) {
    return data[key];
  }

  /** Removes the mapping of the specified value key if this map contains a mapping for the key */
  public void remove(int key) {
    data[key]=-1;
  }
}

@Test
public void test(){
  MyHashMap hashMap = new MyHashMap();
  hashMap.put(1, 1);
  hashMap.put(2, 2);
  System.out.println(hashMap.get(1)); // 返回 1
  System.out.println(hashMap.get(3)); // 返回 -1 (未找到)
  hashMap.put(2, 1); // 更新已有的值
  System.out.println(hashMap.get(2)); // 返回 1
  hashMap.remove(2); // 删除键为2的数据
  System.out.println(hashMap.get(2)); // 返回 -1 (未找到)
}