คู่มือโอลิมปิกคอมพิวเตอร์

Dynamic Array

คำอธิบาย

• dynamic array เป็น array ที่สามารถยืดหดขนาดได้

• ใน STL จะมี vector เป็น dynamic array ให้ใช้

แนวทาง

• เมื่อต้องการเพิ่มข้อมูลลงในอาเรย์ แต่อาเรย์นั้นเต็มแล้ว ให้สร้างฟังก์ชันโดย

• ฟังก์ชันนั้นสร้างอาเรย์ขนาดสองเท่าจากเดิม และคัดลอกข้อมูลจากอาเรย์เดิมมาใส่

การเพิ่มข้อมูล

• หากมีการขยายขนาดอาเรย์และคัดลอกข้อมูลจะทำให้ใช้เวลา O(n)

• แต่กรณีนี้เกิดขึ้นเมื่ออาเรย์เต็มเท่านั้น

• ดังนั้นในกรณีส่วนมากยังใช้เวลาเป็น O(1) อยู่ดี

• ด้วย amortized analysis สามารถถัวเฉลี่ยการเพิ่มข้อมูลเป็น O(1) ได้

Delete Element

• การลบข้อมูลสามารถทำได้ตามปกติเหมือนอาเรย์ทั่วไป

• ในทางทฤษฎี สามารถลดขนาดอาเรย์ลงได้ แต่ไม่จำเป็นใน competitive programming

ตัวอย่าง implementation แบบไม่ใช้ vector

#include <bits/stdc++.h>

using namespace std;

int cnt = 0;
int sz = 1;
int *A = new int[sz];

void add(int x) {
  if (cnt == sz) {
    sz *= 2;
    int *tmp = new int[sz];
    for (int i = 0; i < cnt; i++) {
      tmp[i] = A[i];
    }
    free(A);
    A = tmp;
  }
  A[cnt++] = x;
}

void remove() { cnt--; }

void removeAt(int j) {
  for (int i = j; i < cnt; i++) {
    A[i] = A[i + 1];
  }
  cnt--;
}

void print() {
  printf("sz = %d, cnt = %d\\n", sz, cnt);
  for (int i = 0; i < cnt; i++) {
    printf("%d ", A[i]);
  }
  printf("\\n");
}

int main() {
  add(1);
  print();
  add(2);
  print();
  add(3);
  print();
  add(4);
  add(5);
  print();
  add(6);
  print();
  remove();
  print();
  removeAt(3);
  print();
}