C语言刷题 LeetCode 30天挑战 （一）

LeetCode C language train，Day1 

issue
Given a non-empty array of integers, every element appears twice except for one. Find that single one
Your algorithm should have a linear runtime complexity, Could you implement it without using extra memory?
Input:[2,2,1]                Output:1
Input:[4,1,2,1,2]          Output:4

Function prototypes

int singleNumber(int *nums,int numsSize){
}

写法1：

int singleNumber(int *nums,int numsSize){
    for (int i=0 ; i<numsSize ; ++i){  
        int count = 0;
        for ( int j=0 ; j<numsSize ; ++j ){
            if(nums[i] == nums[j]){
                count++;
            }
        }
        if(count == 1)
            return nums[i];
    }
    return -1;
}

时间复杂度高，当前实现的时间复杂度是 O(n^2)，因为它使用了两个嵌套循环来检查每个元素的出现次数。这在 numsSize 较大时会导致性能问题。（我们可以通过空间去换时间，这种办法后续也会提到）

返回值问题：如果输入数组中没有唯一的数字，函数会返回 -1，这可能不是一个合理的返回值，因为它可能与数组中的有效数据冲突。

写法2：

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

在异或运算中，成对的数字会相互抵消（例如，x ^ x = 0），而唯一的数字会保留在 result 中。

可以看到下述内容

原文地址：https://blog.csdn.net/weixin_64593595/article/details/142500452

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！