算法通关村第三关—继续讨论数据问题(黄金)

        继续讨论数据问题

一、数组中出现次数超过一半的数字

 Leetcode 169.多数元素 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如:输入如下所示的一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2(题目保证出现该数)
 剑指offer中的类似题目条件增加:如果该数不存在,则输出0。
 首先,用排序行不行?这里说一定存在出现次数超过一半的数字了,那么先对数组进行排序。在一个有序数组中次数超过一半的必定是中位数,所以可以直接取出中位数。如果不放心,可以再遍历数组,确认一下这个数字是否出现次数超过一半。OK,没问题,第一种方法就出来了。 这种方法的的时间复杂度取决于排序算法的时间复杂度,最快为O(logn)。由于排序的代价比较高,所以我们继续找其他方法。

//按leetcode要求写的,返回0的情况没写
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

 其次,用Hash行不行?我们先创建一个HashMap的key是元素的值,value是已经出现的次数,然后遍历数组来统计所有元素出现的次数。最后再次遍历Hash,找到出现次数超过一半的数字。OK,第二种方法出来了,代码就是:

public int moreThanHalfNum(int[] array){
    if(array == null) return 0;
    Map<Integer,Integer> res = new HashMap<>();
    int len = array.length;
    for(int i = 0; i < array.length; i++){
        res.put(array[i], res.getorDefault(array [i],0) + 1);
        if(res.get(array[i]) > len / 2) return array[i];
    }
    return 0;
}

二、数组中只出现一次的数字

 LeetCode136.给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次,找出那个只出现了一次的元素。
image.png
 这个题貌似使用Set集合比较好,Set集合不存重复值,这一特点可以利用。题目明确说其他元素都是出现两次,我们也可以利用这个操作,当要添加的元素key与集合中已存在的数重复时,不再进行添加操作,而是将集合中的key一起删掉,这样整个数组遍历完后,集合中就只剩下了那个只出现了一次的数字了。

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet();
        for(int num : nums){//if(set.contains(num))写成这样也行
            if(!set.add(num)){
                set.remove(num);
            }
            else set.add(num);
        }
        for(int num : set) return num;
        return 0;
    }
}

 上面要注意,必须存在那个只出现了一次的数字,否则St集合长度将为0,最后一行代码运行时会出错。
 第二种方法:位运算这个题面试官可能还会让你用位运算来做,该怎么办呢?
异或运算的几个规则是:
image.png
 0与其他数字异或的结果是那个数字,相等的数字异或得0。要操作的数组中除了某个数字只出现了一次之外,其他数字都出现了两次,所以可以定义一个变量赋初始值为0,用这个变量与数组中每个数字做异或运算,并将这个变量值更新为那个运算结果,直到数组遍历完毕,最后得到的变量的值就是数组中只出现了一次的数字了。这种方法只需遍历一次数组即可,代码如下:

class Solution {
    public int singleNumber(int[] nums) {
        int num = 0;
        for(int num1 : nums){
            num ^= num1;
        }
        return num;
    }
}

颜色分类问题(荷兰国旗问题)

 我们使用整数0、1和2分别表示红色、白色和蓝色。必须在不使用库的sort函数的情况下解决这个问题。
image.png
 这个题是非常经典的双指针问题,而且还可以使用多种方式的双指针。这里我们分析两种方法,一种与冒泡排序非常类似,一种与快速排序非常类似。

1.基于冒泡排序的双指针(快慢指针)

 冒泡排序我们都知道,就是根据大小逐步和后面的比较,慢慢调整到整体有序。这种方法还是稳定的排序方法。
 我们可以考虑对数组进行两次遍历。在第一次遍历,我们将数组中所有的0交换到数组的头部,这样第二次遍历只需要处理1和2的问题就行了,而这两次寻找本身又是非常漂亮的双指针。代码如下:

public void sortColors(int[] nums){
    int n = nums.length;
    int left = 0;
    //将所有的0交换到数组的最前面,第一次快慢指针
    for(int right = 0; right < n; right++){
        if(nums[right] == 0){
            int temp = nums [right];
            nums[right] = nums [left];
            nums[left] = temp;
            left++;
        }
    }
    //将所有的1交换到2的前面,第二次快慢指针
    for(int right = left; right < n; right++){
        if(nums[right] == 1){
            int temp = nums[right];
            nums[right] = nums[left];
            nums[left] = temp;
            left++;
        }
    }
}

 上面的方式能解决问题,而且效率还不错。但是面试官可能又给你出幺蛾子,能否将两次遍历变成一次搞定?

2.三指针

 我们要使用三个指针才行:
·Ieft指针,表示left左侧的元素都是0
·right指针,表示right右侧的元素都是2
·index指针,从头到尾遍历数组,根据nums[index]是0还是2决定与left交换还是与right交换。
 index位置上的数字代表着我们当前需要处理的数字。当index为数字1的时候,我们什么都不需要做,直接+1即可。如果是0,我们放到左边,如果是2,放到右边。如果index=right,则可以停止。我们看一下图示:
image.png
 这里的重点和难点index位置为2进行交换后为什么只进行right.–,而不用index±+呢?这是因为我们right位置交换过来的元素可能是0,也可能是1。如果是0自然没问题,但是如果是1则执行index++就将1跳过无法处理了。所以我们先不动index,在下一次循环时继续判断这个index位置元素是不是0。
 那为啥index位置是0的时候执行swap就可以index++了呢,这是因为如果index前面位置如果存在位置都会被swap到right位置去了,这里只需要处理0和1的情况就可以了。
代码如下:

public void sortColors(int[] nums){
    int left = 0, right = nums.length - 1;
    int index = 0;
    while(index <= right){
        if (nums[index] == 0)
            swap(nums,  index++, left++);
        else if(nums [index ]== 2)
            swap(nums,index,right--);
        else index++;
    }
}
private void swap(int[]nums,int i,int j){
    int temp=nums [i];
    nums [i]=nums [j];
    nums [j]=temp;
}

3.哈希表

 自己尝试做这道题的时候,首先想到用哈希表的方法,统计0,1,2的个数,然后三次循环给数组赋值

class Solution {
    public void sortColors(int[] nums) {
        // if(nums.length == 0) return;
        // Map<Integer, Integer> map = new HashMap();
        // map.put(0,0);map.put(1,0);map.put(2,0);
        // for(int i = 0; i < nums.length; i++){
        //     map.put(nums[i],map.get(nums[i]) + 1);
        // }
        // for(int i = 0; i < map.get(0); i++) nums[i] = 0;
        // for(int i = map.get(0); i < map.get(0) + map.get(1); i++) nums[i] = 1;
        // for(int i = map.get(0) + map.get(1); i < nums.length; i++) nums[i] = 2;
        int n = nums.length;
    int left = 0;
    //将所有的0交换到数组的最前面
    for(int right = 0; right < n; right++){
        if(nums[right] == 0){
            int temp = nums [right];
            nums[right] = nums [left];
            nums[left] = temp;
            left++;
        }
    }
    //将所有的1交换到2的前面
    for(int right = left; right < n; right++){
        if(nums[right] == 1){
            int temp = nums[right];
            nums[right] = nums[left];
            nums[left] = temp;
            left++;
        }
    }

    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/229310.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

个人博客网站需求分析报告

目录 一. 概述1.1 目的1.2 背景1.3 术语定义 二. 需求分析三. 系统功能需求3.1 功能总览3.2 业务流程图1.系统用例图2.系统流程 四.开发技术4.1 技术组成 五.界面及运行环境1.用户界面2.运行环境 一. 概述 1.1 目的 1.2 背景 1.3 术语定义 二. 需求分析 三. 系统功能需求 …

微软NativeApi-NtQuerySystemInformation

微软有一个比较实用的Native接口&#xff1a;NtQuerySystemInformation&#xff0c;具体可以参考微软msdn官方文档&#xff1a;NtQuerySystemInformation&#xff0c; 是一个系统函数&#xff0c;用于收集特定于所提供的指定种类的系统信息。ProcessHacker等工具使用NtQuerySys…

【matlab程序】matlab画螺旋图|旋转图

%% 数学之美====》螺旋线 % 海洋与大气科学 % 20231205 clear;clc;close all; n=10; t=0:0.01:2pin; R=1; xx=nan(length(t),1);yy=nan(length(t),1); for i=1:length(t) xx(i)=Rcos(t(i)); yy(i)=Rsin(t(i)); R=R+1; end figure set(gcf,‘position’,[50 50 1200 1200],‘col…

【语义分割数据集】——imagenet语义分割

地址&#xff1a;https://github.com/LUSSeg/ImageNet-S 1 例图 2. 类别和数量信息 疑问 根据原文的描述&#xff1a;Based on the ImageNet dataset, we propose the ImageNet-S dataset with 1.2 million training images and 50k high-quality semantic segmentation annot…

实用方法 | 搭建真正满足用户需求的在线帮助中心

随着互联网的普及和信息技术的快速发展&#xff0c;客户服务和支持变得越来越重要。为了提高客户满意度和维持良好的品牌形象&#xff0c;越来越多企业都开始搭建自己的在线帮助中心。 不知从何下手&#xff1f;细想一下&#xff0c;搭建在线帮助中心主要就是为了解决用户的问…

【Angular开发】Angular 16发布:发现前7大功能

Angular 于2023年5月3日发布了主要版本升级版Angular 16。作为一名Angular开发人员&#xff0c;我发现这次升级很有趣&#xff0c;因为与以前的版本相比有一些显著的改进。 因此&#xff0c;在本文中&#xff0c;我将讨论Angular 16的前7个特性&#xff0c;以便您更好地理解。…

12.8 作业 C++

使用手动连接&#xff0c;将登录框中的取消按钮使用qt4版本的连接到自定义的槽函数中&#xff0c;在自定义的槽函数中调用关闭函数 将登录按钮使用qt5版本的连接到自定义的槽函数中&#xff0c;在槽函数中判断ui界面上输入的账号是否为"admin"&#xff0c;密码是否为…

Vue 核心 数据监听 computed | watch

Vue 核心 数据监听 computed | watch 一、今日学习目标 1.指令补充 指令修饰符v-bind对样式增强的操作v-model应用于其他表单元素 2.computed计算属性 基础语法计算属性vs方法计算属性的完整写法成绩案例 3.watch侦听器 基础写法完整写法 4.综合案例 &#xff08;演示&…

视频剪辑:视频转码实用技巧,批量将MP4转为MP3音频

随着数字媒体设备的普及&#xff0c;视频和音频文件已成为日常生活中的重要组成部分。有时&#xff0c;可能要将MP4视频文件转换为MP3音频文件&#xff0c;以提取其中的音频内容或者进行其他处理。这是耗费时间的任务&#xff0c;那要如何操作呢&#xff1f;本文详解云炫AI智剪…

使用pytorch查看中间层特征矩阵以及卷积核参数

这篇是我对哔哩哔哩up主 霹雳吧啦Wz 的视频的文字版学习笔记 感谢他对知识的分享 1和4是之前讲过的alexnet和resnet模型 2是分析中间层特征矩阵的脚本 3是查看卷积核参数的脚本 1设置预处理方法 和图像训练的时候用的预处理方法保持一致 2实例化模型 3载入之前的模型参数 4载入…

C#网络编程(System.Net命名空间)

目录 一、System.Net命名空间 1.Dns类 &#xff08;1&#xff09;示例源码 &#xff08;2&#xff09;生成效果 2.IPAddress类 &#xff08;1&#xff09;示例源码 &#xff08;2&#xff09;生成效果 3.IPEndPoint类 &#xff08;1&#xff09; 示例源码 &#xff0…

计算机方向的一些重要缩写和简介

参考&#xff1a; 深度学习四大类网络模型 干货|机器学习超全综述&#xff01; 机器学习ML、卷积神经网络CNN、循环神经网络RNN、马尔可夫蒙特卡罗MCMC、生成对抗网络GAN、图神经网络GNN——人工智能经典算法 MLP&#xff08;Multi Layer Perseption&#xff09;用在神经网络中…

Conda常用命令总结

使用conda或anaconda的小伙伴们都知道&#xff0c;图形界面时不靠谱的&#xff0c;而在命令行下&#xff0c;所有的操作就会稳定很多&#xff0c;且极少出现问题。因此&#xff0c;熟记conda的命令行就变得十分有用。但对于我这样近50岁依旧奋斗在代码第一线的大龄程序员而已&a…

作业12.8

1. 使用手动连接&#xff0c;将登录框中的取消按钮使用qt4版本的连接到自定义的槽函数中&#xff0c;在自定义的槽函数中调用关闭函数。将登录按钮使用qt5版本的连接到自定义的槽函数中&#xff0c;在槽函数中判断ui界面上输入的账号是否为"admin"&#xff0c;密码是…

HarmonyOS Developer——鸿蒙【构建第一个JS应用(FA模型)】

创建JS工程 JS工程目录结构 构建第一个页面 构建第二个页面 实现页面间的跳转 使用真机运行应用 说明 为确保运行效果&#xff0c;本文以使用DevEco Studio 3.1 Release版本为例&#xff0c;点击此处获取下载链接。 创建JS工程 若首次打开DevEco Studio&#xff0c;请点击…

C# Solidworks二次开发:选择管理器相关的API介绍

今天在讲述主要内容之前&#xff0c;先说一个不太相关的问题。 我之前在其他文章中看到有一些朋友在问为什么获取到的点位数据需要乘以1000进行单位转换&#xff0c;其实原因是这样的&#xff0c;在所有使用的API中如果没有特殊说明&#xff0c;所有的长度单位都是米&#xff…

解读链上经济“一等公民”:加密AI代理的优势和前沿应用

机器人正在成为加密经济的“一等公民”&#xff0c;最近的案例就能印证这一趋势。 搜索者&#xff08;Searchers&#xff09;部署像Jaredfromsubway.eth这样的机器人&#xff0c;利用真人用户对便利的渴望在DEX抢先交易。Banana Gun和Maestro允许真人用户通过Telegram的便利进…

网络编程基础api

1. IP 协议 1.1 IP 分片 &#xff08;1&#xff09;IP 分片和重组主要依靠 IP 头部三个字段&#xff1a;数据报标识、标志和片偏移 以太网帧的 MTU 是 1500 字节&#xff1b; 一个每个分片都有自己的 IP 头部&#xff0c;它们都具有相同的标识值&#xff0c;有不同的片偏移…

MVC、MVP、MVVM模式的区别

前言&#xff1a;这三个表现层框架设计模式是依次进化而形成MVC—>MVP—>MVVM。在以前传统的开发模式当中即MVC模式&#xff0c;前端人员只负责Model&#xff08;数据库&#xff09;、 View&#xff08;视图&#xff09;和 Controller /Presenter/ViewModel&#xff08;控…

【SQL开发实战技巧】系列(四十八):Oracle12C常用新特性☞多分区操作和管理

系列文章目录 【SQL开发实战技巧】系列&#xff08;一&#xff09;:关于SQL不得不说的那些事 【SQL开发实战技巧】系列&#xff08;二&#xff09;&#xff1a;简单单表查询 【SQL开发实战技巧】系列&#xff08;三&#xff09;&#xff1a;SQL排序的那些事 【SQL开发实战技巧…