首页 > 其他分享 >136. 只出现一次的数字

136. 只出现一次的数字

时间:2023-10-15 21:35:34浏览次数:43  
标签:count 一次 return 数字 nums int ++ 136 size

1.题目简介

2.题解

本题思路参考了某位大大的题解,链接:https://leetcode.cn/problems/single-number/solutions/5118/xue-suan-fa-jie-guo-xiang-dui-yu-guo-cheng-bu-na-y/

2.1 数组/哈希表解法

思路

这里很容易想法就是成对存储:数(键)和数出现的次数(键值),所以使用数组和哈希表存储都是比较容易想到的。
但是有一个关键问题(且该算法只使用常量额外空间),而这两种方法都要使用额外的空间,空间代价为o(n)

代码(这里只展示使用哈希表的解法,数组思路同理)

class Solution {
public:
    int singleNumber(std::vector<int>& nums) {
        std::unordered_map<int,int> map;
        for (int num:nums){
            map[num]++;
        }
        for (auto pair:map){
            if (pair.second == 1) return pair.first;
        }
        return 0;
    }
};

结果展示

这里是能过通过测试用例的,但是明显空间使用率过低

2.2暴力枚举

思路

如果想要减少空间使用,那就并不能使用数组/哈希表记录每个元素的出现次数,也就是一个时间点,我最多只能知道一个元素的出现次数
很容易想到的便是暴力枚举(两层for循环),外层循环从数组中挑出一个元素,内层循环将其与数组全员(除本身外)比较,若有相同即return

代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++){
            for(int j = 0; j < nums.size(); j++)
            {
                if (nums[i] == nums[j] && i != j) break;
                else if(j == nums.size() - 1) return nums[i];
            }
        }
        return false;
    }
};

结果展示

并没有通过,因为这里的时间代价是o(n^2),超出了时间限制

2.3 快排+寻找

思路

如何将时间代价从o(n^2)减少到o(n)是最大的问题,快排可以将时间代价减少到O(nlogn)
这里是可以在快排途中判断并且获取答案的,这里博主偷懒,直接使用了封装好的快排,在之后进行判断;
总体算两部分,快排O(nlogn),寻找o(n),结合一下时间代价还是O(nlogn)

代码

class Solution {
public:
    int singleNumber(std::vector<int>& nums) {
        int count = 0;
        std::sort(nums.begin(),nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (i == nums.size() - 1 && count == 0) return nums[i];
            if (nums[i] == nums[i+1]) count++;
            else if(count) count = 0;
            else return nums[i];
        }
        return false;
    }
};

结果展示

2.4 异或(最优解)

思路

这里主要利用异或归零律和交换律,恒等律

举个例子就懂了

代码

class Solution {
public:
    int singleNumber(std::vector<int>& nums) {
        int temp = nums[0];
        for (int i = 1; i < nums.size(); i++){
            temp = temp ^ nums[i];
        }
        return temp;
    }
};

结果展示

标签:count,一次,return,数字,nums,int,++,136,size
From: https://www.cnblogs.com/trmbh12/p/17766109.html

相关文章

  • 【gdb】让catchpoint只触发一次
    让catchpoint只触发一次1.例子:#include<stdio.h>#include<stdlib.h>#include<sys/types.h>#include<unistd.h>intmain(void){pid_tpid;inti=0;for(i=0;i<2;i++){ pid=fork(); if(pid<0)......
  • 数字游戏学习对学生数学学习自我效能感、动机、焦虑和成绩的影响
    (Effectsofdigitalgame-basedlearningonstudents’selfefficacy,motivation,anxiety,andachievementsinlearningmathematics) BeijingNormalUniversity2014一、摘要研究目的:本研究在电子书上开发了一个基于数学游戏的学习环境,帮助儿童减少数学焦虑,提高数学学......
  • 罗马数字转阿拉伯数字
    罗马数字转阿拉伯数字目录问题的回答个人理解基于AI学号转换程序部分问题的回答个人理解罗马数字不是位置计数,基于对这两篇文章的理解罗马数字技术规则和位置计数法可总结为:,而罗马数字是不同数字间的和差运算,不属于位置计数法缺点:罗马数字没有表示零的数字,同时书写繁难,不能进......
  • 力扣---137. 只出现一次的数字 II
    给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。 示例1:输入:nums=[2,2,3,2]输出:3示例2:输入:nums=[0,1,0,1,0,1,99]......
  • 136. 只出现一次的数字
    题目题解考察的是位运算——异或(^),相同为0,不同为11^0=1,1^1=0则直接对数据所有元素执行^操作,最终的就是结果classSolution{publicintsingleNumber(int[]nums){intres=0;for(intnum:nums){res=res^num;......
  • 13. 罗马数字转整数
    1.题目介绍罗马数字包含以下七种字符:I,V,X,L,C,D和M。字符数值I1V5X10L50C100D500M1000例如,罗马数字2写做II,即为两个并列的1。12写做XII,即为X+I......
  • Socks5代理与代理IP在数字世界的应用
    随着数字化浪潮的席卷,网络工程师的角色日益关键,他们需要应对跨界电商、爬虫数据采集、出海业务拓展以及游戏体验优化等多方面的挑战。在这一场数字变革的浪潮中,Socks5代理和代理IP成为了网络工程师手中的得力利器,帮助他们处理各种复杂的技术问题。本文将深入探讨这两种技术在数字世......
  • Socks5代理与代理IP在数字世界的应用
    随着数字化浪潮的席卷,网络工程师的角色日益关键,他们需要应对跨界电商、爬虫数据采集、出海业务拓展以及游戏体验优化等多方面的挑战。在这一场数字变革的浪潮中,Socks5代理和代理IP成为了网络工程师手中的得力利器,帮助他们处理各种复杂的技术问题。本文将深入探讨这两种技术在数字世......
  • 第一次接触计算机语言以及对未来的学习计划
       大家好,我是来自广州某大学的一名计算机初学者,同时也是一名新进小比特,很高兴能和大家在这里相遇,对于怎样学习计算机语言,我相信也有不少的兄弟们会有困感,对此我想在此分享自己的一些愚见。 首先,要制定相定的编程目标,你在学习编程语言的路上能走多远取决于你是否有兴趣去认......
  • 学习C语言心得-自定义函数-每调用一次函数 num的值+1
    每调用一次函数num的值+1#include<stdio.h>NUM(int*num){ (*num)++;}intmain(){ intnum=0; NUM(&num); printf("%d\n",num); NUM(&num); printf("%d\n",num); NUM(&num); printf("%d\n",num); NUM(&num)......