04.md

General Skill Counter and Pointer

Counter

Example: Intersection Problem 有兩個任意長度的 array, 找出同時存在兩個 array 裡面的數值 ex: intersection([1, 2, 3], [1, 3, 6]) => [1, 3]

Code:

時間複雜度為 O(nm) = O(n^2)

function intersection(arr1, arr2) {
  let result = [];
  for (let i = 0; i < arr1.length; i++) {
    for (let j = 0; j < arr2.length; j++) {
      if (arr1[i] === arr2[j]) {
        result.push(arr1[i]);
      }
    } 
  }
  return result;
}

使用 Counter 的範例:

時間複雜度為 O(n+m) = O(n)

function intersection(arr1, arr2) {
  let result = [];
  let counter = {};
  const arr3 = arr1.concat(arr2);
  for (let i = 0; i < arr3.length; i++) {
    if (counter[arr3[i]] !== undefined) {
      counter[arr3[i]]++;
    } else {
      counter[arr3[i]] = 1;
    }
  }
  for (let p in counter) {
    if (counter[p] > 1) {
      result.push(p);
    }
  }
  return result;
}

---

Pointer

Example: Average Pair 給定一個排序的 array 與一個平均數值，找出一對數列等於平均數值 ex: averagePair([0, 1, 3, 4, 5], 1.5) => [0, 3]

Code:

時間複雜度為 O(nm) = O(n^2)

function averagePair(arr, avg) {
  let result = [];
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if ((arr[i] + arr[j]) / 2 === avg) {
        result.push([arr[i], arr[j]]);
      }
    } 
  }
  return result;
}

使用 Pointer 的範例:

時間複雜度為 O(n)

function averagePair(arr, avg) {
  let result = [];
  let left = 0;
  let right = arr.length - 1;

  while (right > left) {
    const value = (arr[left] + arr[right]) / 2;
    if (value > avg) {
      right--;
    } else if (value < avg) {
      left++;
    } else if (value === avg) {
      result.push([arr[left], arr[right]]);
      right--;
      left++;
    }
  }
  return result;
}