Question

1426. Counting Elements

中文文档

Description

Given an integer array arr, count how many elements x there are, such that x + 1 is also in arr. If there are duplicates in arr, count them separately.

 

Example 1:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there is no 2, 4, 6, or 8 in arr.

 

Constraints:

• 1 <= arr.length <= 1000
• 0 <= arr[i] <= 1000

Solutions

Solution 1: Counting

We can use a hash table or array $cnt$ to record the frequency of each number in the array $arr$. Then, we traverse each number $x$ in $cnt$. If $x+1$ also exists in $cnt$, we add $cnt[x]$ to the answer.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $arr$.

class Solution:
  def countElements(self, arr: List[int]) -> int:
    cnt = Counter(arr)
    return sum(v for x, v in cnt.items() if cnt[x + 1])

class Solution {
  public int countElements(int[] arr) {
    int[] cnt = new int[1001];
    for (int x : arr) {
      ++cnt[x];
    }
    int ans = 0;
    for (int x = 0; x < 1000; ++x) {
      if (cnt[x + 1] > 0) {
        ans += cnt[x];
      }
    }
    return ans;
  }
}

class Solution {
public:
  int countElements(vector<int>& arr) {
    int cnt[1001]{};
    for (int x : arr) {
      ++cnt[x];
    }
    int ans = 0;
    for (int x = 0; x < 1000; ++x) {
      if (cnt[x + 1]) {
        ans += cnt[x];
      }
    }
    return ans;
  }
};

func countElements(arr []int) (ans int) {
  mx := slices.Max(arr)
  cnt := make([]int, mx+1)
  for _, x := range arr {
    cnt[x]++
  }
  for x := 0; x < mx; x++ {
    if cnt[x+1] > 0 {
      ans += cnt[x]
    }
  }
  return
}

function countElements(arr: number[]): number {
  const mx = Math.max(...arr);
  const cnt = Array(mx + 1).fill(0);
  for (const x of arr) {
    ++cnt[x];
  }
  let ans = 0;
  for (let i = 0; i < mx; ++i) {
    if (cnt[i + 1] > 0) {
      ans += cnt[i];
    }
  }
  return ans;
}

use std::collections::HashMap;

impl Solution {
  pub fn count_elements(arr: Vec<i32>) -> i32 {
    let mut cnt = HashMap::new();
    for &num in &arr {
      *cnt.entry(num).or_insert(0) += 1;
    }
    cnt.iter()
      .filter(|(&x, _)| cnt.contains_key(&(x + 1)))
      .map(|(_, &v)| v)
      .sum()
  }
}

/**
 * @param {number[]} arr
 * @return {number}
 */
var countElements = function (arr) {
  const mx = Math.max(...arr);
  const cnt = Array(mx + 1).fill(0);
  for (const x of arr) {
    ++cnt[x];
  }
  let ans = 0;
  for (let i = 0; i < mx; ++i) {
    if (cnt[i + 1] > 0) {
      ans += cnt[i];
    }
  }
  return ans;
};

class Solution {
  /**
   * @param Integer[] $arr
   * @return Integer
   */
  function countElements($arr) {
    $cnt = array_count_values($arr);
    $ans = 0;
    foreach ($cnt as $x => $v) {
      if (isset($cnt[$x + 1])) {
        $ans += $v;
      }
    }
    return $ans;
  }
}