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 <= 10000 <= 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.
PythonJavaC++GoTypeScriptRustJavaScriptPHP
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])(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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()
}
}(code-box)
/**
* @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;
};(code-box)
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;
}
}(code-box)
