Counting Elements-元素计数 - LeetCode
【摘要】 Contents问题：解题思路：C:方案：测试案例：C++:方案：测试案例：C#:方案：测试案例：Go方案：测试案例：Java:方案：测试案例：Javascript方案：测试案例：Kotlin:方案：测试案例：Python3:方案：测试案例：Rust方案：测试案例： 问题：Given an integer array arr, count element x such that x + 1...
Contents
问题：
Given an integer array arr, count element x such that x + 1 is also in arr.
If there're duplicates in arr, count them seperately.
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's no 2, 4, 6, or 8 in arr.
Example 3:
Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.
Example 4:
Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.
Constraints:
- 1 <= arr.length <= 1000
- 0 <= arr[i] <= 1000
解题思路：
这个问题的解题思路如下：
1. 遍历数组元素，存入一个HashSet中，时间复杂度O(n);
2. 遍历数组元素，每个元素加1以后检查存在于HashSet中，并增加计数，时间复杂度O(n);
3. 返回结果，总的时间复杂度为O(n);
C:
方案：
C中没有类似hashset数据结构，只好使用循环的方式查找。
int countElements(int* arr, int arrSize) {
int count = 0;
for (int i = 0; i < arrSize; i++)
{
int v = arr[i] + 1;
for (int j = 0; j < arrSize; j++) {
if (v == arr[j]) {
count++;
break;
}
}
}
return count;
}测试案例：
TEST_METHOD(TestMethod1)
{
int arr[] = { 1,2,3 };
int result = countElements(arr, sizeof(arr) / sizeof(arr[0]));
int expected = 2;
Assert::AreEqual(result, expected);
}
TEST_METHOD(TestMethod2)
{
int arr[] = { 1,1,3,3,5,5,7,7 };
int result = countElements(arr, sizeof(arr) / sizeof(arr[0]));
int expected = 0;
Assert::AreEqual(result, expected);
}
TEST_METHOD(TestMethod3)
{
int arr[] = { 1,3,2,3,5,0 };
int result = countElements(arr, sizeof(arr) / sizeof(arr[0]));
int expected = 3;
Assert::AreEqual(result, expected);
}
TEST_METHOD(TestMethod4)
{
int arr[] = { 1,1,2,2 };
int result = countElements(arr, sizeof(arr) / sizeof(arr[0]));
int expected = 2;
Assert::AreEqual(result, expected);
}C++:
方案：
class Solution {
public:
int countElements(vector<int>& arr) {
unordered_set<int> set;
for (auto v : arr) {
set.insert(v);
}
int count = 0;
for (auto v : arr) {
int t = v + 1;
if (set.find(t) != set.end()) {
count++;
}
}
return count;
}
};测试案例：
TEST_METHOD(TestMethod1) {
Solution solution;
int numsArray[] = { 1,2,3 };
vector<int> nums;
nums.insert(nums.begin(), begin(numsArray), end(numsArray));
int result = solution.countElements(nums);
int expected = 2;
Assert::AreEqual(result, expected);
}
TEST_METHOD(TestMethod2) {
Solution solution;
int numsArray[] = { 1,1,3,3,5,5,7,7 };
vector<int> nums;
nums.insert(nums.begin(), begin(numsArray), end(numsArray));
int result = solution.countElements(nums);
int expected = 0;
Assert::AreEqual(result, expected);
}
TEST_METHOD(TestMethod3) {
Solution solution;
int numsArray[] = { 1,3,2,3,5,0 };
vector<int> nums;
nums.insert(nums.begin(), begin(numsArray), end(numsArray));
int result = solution.countElements(nums);
int expected = 3;
Assert::AreEqual(result, expected);
}
TEST_METHOD(TestMethod4) {
Solution solution;
int numsArray[] = { 1,1,2,2 };
vector<int> nums;
nums.insert(nums.begin(), begin(numsArray), end(numsArray));
int result = solution.countElements(nums);
int expected = 2;
Assert::AreEqual(result, expected);
}C#:
方案：
public class Solution
{
public int CountElements(int[] arr)
{
HashSet<int> hs = new HashSet<int>();
foreach (int v in arr)
{
hs.Add(v);
}
int count = 0;
foreach (int v in arr)
{
if (hs.Contains(v + 1))
{
count++;
}
}
return count;
}
}
测试案例：
[TestMethod()]
public void Test1()
{
Solution solution = new Solution();
int[] nums = { 1, 2, 3 };
int result = solution.CountElements(nums);
int expected = 2;
Assert.AreEqual(expected, result);
}
[TestMethod()]
public void Test2()
{
Solution solution = new Solution();
int[] nums = { 1, 1, 3, 3, 5, 5, 7, 7 };
int result = solution.CountElements(nums);
int expected = 0;
Assert.AreEqual(expected, result);
}
[TestMethod()]
public void Test3()
{
Solution solution = new Solution();
int[] nums = { 1, 3, 2, 3, 5, 0 };
int result = solution.CountElements(nums);
int expected = 3;
Assert.AreEqual(expected, result);
}
[TestMethod()]
public void Test4()
{
Solution solution = new Solution();
int[] nums = { 1, 1, 2, 2 };
int result = solution.CountElements(nums);
int expected = 2;
Assert.AreEqual(expected, result);
}Go
func countElements(arr []int) int {
count := 0
m := make(map[int]bool)
for _, v := range arr {
m[v] = true
}
for _, v := range arr {
if _, ok := m[v+1]; ok {
count++
}
}
return count
}
}
方案：
测试案例：
func Test_countElements(t *testing.T) {
type args struct {
arr []int
}
tests := []struct {
name string
args args
want int
}{
{"test1", args{arr: []int{1, 2, 3}}, 2},
{"test2", args{arr: []int{1, 1, 3, 3, 5, 5, 7, 7}}, 0},
{"test3", args{arr: []int{1, 3, 2, 3, 5, 0}}, 3},
{"test3", args{arr: []int{1, 1, 2, 2}}, 2},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
if got := countElements(tt.args.arr); got != tt.want {
t.Errorf("countElements() = %v, want %v", got, tt.want)
}
})
}
}Java:
方案：
class Solution {
public int countElements(int[] arr) {
Set<Integer> hs = new HashSet<Integer>();
for (int v : arr) {
hs.add(v);
}
int count = 0;
for (int v : arr) {
if (hs.contains(v + 1)) {
count++;
}
}
return count;
}
}
测试案例：
@Test
public void test1() {
Solution solution = new Solution();
int[] nums = new int[] { 1, 2, 3 };
int result = solution.countElements(nums);
int expected = 2;
Assert.assertEquals(result, expected);
}
@Test
public void test2() {
Solution solution = new Solution();
int[] nums = new int[] { 1, 1, 3, 3, 5, 5, 7, 7 };
int result = solution.countElements(nums);
int expected = 0;
Assert.assertEquals(result, expected);
}
@Test
public void test3() {
Solution solution = new Solution();
int[] nums = new int[] { 1, 3, 2, 3, 5, 0 };
int result = solution.countElements(nums);
int expected = 3;
Assert.assertEquals(result, expected);
}
@Test
public void test4() {
Solution solution = new Solution();
int[] nums = new int[] { 1, 1, 2, 2 };
int result = solution.countElements(nums);
int expected = 2;
Assert.assertEquals(result, expected);
}Javascript
方案：
测试案例：
/**
* @param {number[]} arr
* @return {number}
*/
var countElements = function(arr) {
let set = new Set();
arr.forEach(x=>{
set.add(x);
});
let count = 0;
arr.forEach(x=>{
if(set.has(x+1)) {
count ++;
}
});
return count;
};测试案例：
it("test1", function () {
// 1. ARRANGE
let nums = [1, 2, 3];
let expected = 2;
// 2. ACT
let result = countElements(nums);
// 3. ASSERT
expect(result).to.be.equal(expected);
});
it("test2", function () {
// 1. ARRANGE
let nums = [1, 1, 3, 3, 5, 5, 7, 7];
let expected = 0;
// 2. ACT
let result = countElements(nums);
// 3. ASSERT
expect(result).to.be.equal(expected);
});
it("test3", function () {
// 1. ARRANGE
let nums = [1, 3, 2, 3, 5, 0];
let expected = 3;
// 2. ACT
let result = countElements(nums);
// 3. ASSERT
expect(result).to.be.equal(expected);
});
it("test4", function () {
// 1. ARRANGE
let nums = [ 1, 1, 2, 2 ];
let expected = 2;
// 2. ACT
let result = countElements(nums);
// 3. ASSERT
expect(result).to.be.equal(expected);
});
Kotlin:
class Solution {
fun countElements(arr: IntArray): Int {
val set: MutableSet<Int> = HashSet()
for (i in 0 until arr.size) {
set.add(arr[i])
}
var count = 0;
for (i in 0 until arr.size) {
if(set.contains(arr[i] + 1)) {
count ++
}
}
return count
}
}
测试案例：
@Test
fun test1() {
val solution = Solution()
val nums = intArrayOf(1, 2, 3)
val result = solution.countElements(nums)
val expected = 2
Assert.assertEquals(result, expected)
}
@Test
fun test2() {
val solution = Solution()
val nums = intArrayOf(1, 1, 3, 3, 5, 5, 7, 7)
val result = solution.countElements(nums)
val expected = 0
Assert.assertEquals(result, expected)
}
@Test
fun test3() {
val solution = Solution()
val nums = intArrayOf(1, 3, 2, 3, 5, 0)
val result = solution.countElements(nums)
val expected = 3
Assert.assertEquals(result, expected)
}
@Test
fun test4() {
val solution = Solution()
val nums = intArrayOf(1, 1, 2, 2 )
val result = solution.countElements(nums)
val expected = 2
Assert.assertEquals(result, expected)
}Python3:
方案：
class Solution:
def countElements(self, arr: List[int]) -> int:
s = set()
for v in arr:
s.add(v)
count = 0
for v in arr:
if (v+1 in s):
count = count + 1
return count测试案例：
def test_1(self):
s = Solution()
self.assertEqual(s.countElements([1, 2, 3]), 2)
def test_2(self):
s = Solution()
self.assertEqual(s.countElements([1, 1, 3, 3, 5, 5, 7, 7]), 0)
def test_3(self):
s = Solution()
self.assertEqual(s.countElements([1, 3, 2, 3, 5, 0]), 3)
def test_4(self):
s = Solution()
self.assertEqual(s.countElements([1, 1, 2, 2]), 2) Rust
方案：
impl Solution {
pub fn count_elements(arr: Vec<i32>) -> i32 {
let mut hs = std::collections::HashSet::new();
for (_pos, e) in arr.iter().enumerate() {
hs.insert(e);
}
let mut count = 0;
for (_pos, e) in arr.iter().enumerate() {
let t = e+1;
if hs.contains(&t) {
count +=1;
}
}
return count;
}
}测试案例：
#[test]
fn test1() {
let vec = vec![1, 2, 3];
let result = Solution::count_elements(vec);
let expected = 2;
assert_eq!(result, expected);
}
#[test]
fn test2() {
let vec = vec![1, 1, 3, 3, 5, 5, 7, 7];
let result = Solution::count_elements(vec);
let expected = 0;
assert_eq!(result, expected);
}
#[test]
fn test3() {
let vec = vec![1, 3, 2, 3, 5, 0];
let result = Solution::count_elements(vec);
let expected = 3;
assert_eq!(result, expected);
}
#[test]
fn test4() {
let vec = vec![1, 1, 2, 2];
let result = Solution::count_elements(vec);
let expected = 2;
assert_eq!(result, expected);
} 
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）