Day1-1 leetcode 136 :Single numble

Albert_xiong

发布于 2021-06-21 17:56:45

2220

发布于 2021-06-21 17:56:45

文章被收录于专栏：Mybatis学习

合理采用位运算 Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

两种解法，第一个是嵌套循环遍历，但是时间复杂度较高，消耗了太多的内存

C语言形式：

方法一：

int singleNumber(int* nums, int numsSize)
{
	//遍历数组中的元素
    for(int i=0;i<numsSize;i++)
    {
    	//定义一个计数的count
        int count =0;
        //第二次遍历，统计字符出现的次数
        for(int j =0;j<numsSize;j++)
        {
            if(nums[j]==nums[i])
                count ++;
        }
        //如果计数只有一个，则返回对应的元素
        if(count == 1)
            return nums[i];
    }
    return -1;
}

方法二：位运算，时间复杂度和空间复杂度较低

int singleNumber(int* nums, int numsSize)
{
    int n = nums[0];
    for(int i =1;i<numsSize;i++)
    {
        n = n^nums[i];
    }
    return n;
}

Python形式：

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = nums[0]
        for i in range(1,len(nums)):
            n = n^nums[i]
        return n

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/12/09 ，如有侵权请联系 cloudcommunity@tencent.com 删除

python