README.md

1426. 数元素

English Version

题目描述

给你一个整数数组 arr， 对于元素 x ，只有当 x + 1 也在数组 arr 里时，才能记为 1 个数。

如果数组 arr 里有重复的数，每个重复的数单独计算。

 

示例 1：

输入：arr = [1,2,3]
输出：2
解释：1 和 2 被计算次数因为 2 和 3 在数组 arr 里。

示例 2：

输入：arr = [1,1,3,3,5,5,7,7]
输出：0
解释：所有的数都不算, 因为数组里没有 2、4、6、8。

 

提示：

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

解法

方法一：暴力枚举

枚举 arr 的每个元素 x，判断 x+1 是否在 arr 中，是则累加答案。

时间复杂度 $O(n^2)$，空间复杂度 $O(1)$。

方法二：哈希表

将 arr 所有元素放入哈希表 s 中。然后遍历 arr 的每个元素 x，判断 x+1 是否在 s 中，是则累加答案。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

Python3

class Solution:
    def countElements(self, arr: List[int]) -> int:
        return sum(x + 1 in arr for x in arr)

class Solution:
    def countElements(self, arr: List[int]) -> int:
        s = set(arr)
        return sum(x + 1 in s for x in arr)

Java

class Solution {
    public int countElements(int[] arr) {
        int ans = 0;
        for (int x : arr) {
            for (int v : arr) {
                if (x + 1 == v) {
                    ++ans;
                    break;
                }
            }
        }
        return ans;
    }
}

class Solution {
    public int countElements(int[] arr) {
        Set<Integer> s = new HashSet<>();
        for (int num : arr) {
            s.add(num);
        }
        int res = 0;
        for (int num : arr) {
            if (s.contains(num + 1)) {
                ++res;
            }
        }
        return res;
    }
}

C++

class Solution {
public:
    int countElements(vector<int>& arr) {
        int ans = 0;
        for (int x : arr) {
            for (int v : arr) {
                if (x + 1 == v) {
                    ++ans;
                    break;
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    int countElements(vector<int>& arr) {
        unordered_set<int> s(arr.begin(), arr.end());
        int ans = 0;
        for (int x : arr) {
            ans += s.count(x + 1);
        }
        return ans;
    }
};

Go

func countElements(arr []int) int {
	ans := 0
	for _, x := range arr {
		for _, v := range arr {
			if x+1 == v {
				ans++
				break
			}
		}
	}
	return ans
}

func countElements(arr []int) int {
	s := map[int]bool{}
	for _, x := range arr {
		s[x] = true
	}
	ans := 0
	for _, x := range arr {
		if s[x+1] {
			ans++
		}
	}
	return ans
}

JavaScript

/**
 * @param {number[]} arr
 * @return {number}
 */
var countElements = function (arr) {
    let ans = 0;
    for (const x of arr) {
        ans += arr.includes(x + 1);
    }
    return ans;
};

/**
 * @param {number[]} arr
 * @return {number}
 */
var countElements = function (arr) {
    const s = new Set();
    for (const x of arr) {
        s.add(x);
    }
    let ans = 0;
    for (const x of arr) {
        if (s.has(x + 1)) {
            ++ans;
        }
    }
    return ans;
};

PHP

class Solution {
    /**
     * @param Integer[] $arr
     * @return Integer
     */
    function countElements($arr) {
        $cnt = 0;
        for ($i = 0; $i < count($arr); $i++) {
            if (in_array($arr[$i] + 1, $arr)) {
                $cnt++;
            }
        }
        return $cnt++;
    }
}

...