Counting Elements-元素计数 - LeetCode

举报
Jet Ding 发表于 2021/07/26 10:21:11 2021/07/26
【摘要】 Contents问题:解题思路:C:方案:测试案例:C++:方案:测试案例:C#:方案:测试案例:Go方案:测试案例:Java:方案:测试案例:Javascript方案:测试案例:Kotlin:方案:测试案例:Python3:方案:测试案例:Rust方案:测试案例:  问题:Given an integer array arr, count element x such that x + 1...

Contents

问题:

解题思路:

C:

方案:

测试案例:

C++:

方案:

测试案例:

C#:

方案:

测试案例:

Go

方案:

测试案例:

Java:

方案:

测试案例:

Javascript

方案:

测试案例:

Kotlin:

方案:

测试案例:

Python3:

方案:

测试案例:

Rust

方案:

测试案例:

 

 

问题:

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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。