文档章节

算法:有序数组删除重复元素,和查找等值键的问题

gaomq
 gaomq
发布于 2017/06/03 14:30
字数 492
阅读 7
收藏 0
点赞 0
评论 0

使用二分查找法删除数组中重复的元素,首先我们来回顾下二分查找法。有两种实现,一种是递归一种是非递归的。

递归实现

 public static int BinarySearch(int key, int[] a, int lo, int hight) {
        if (lo > hight) {
            return -1;
        }
        // 获取数组中间位置
        int mid = lo + (hight - lo) / 2;
        if (key < a[mid]) {
            return BinarySearch(key, a, lo, mid - 1);
        } else if (key > a[mid]) {
            return BinarySearch(key, a, mid + 1, hight);
        } else
            return a[mid];
    }

非递归实现

public static int BinarySearch(int key, int[] a) {
        int lo = 0;
        int hight = a.length - 1;
        while (lo <= hight) {
            int mid = lo + (hight - lo) / 2;
            if (key < a[mid])
                hight = mid - 1;
            else if (key > a[mid])
                lo = mid + 1;
            else
                return a[mid];
        }
        return -1;
    }

在有序的数组中我们该怎么样去删除重复的元素,怎么样获取重复元素的个数?

查找首次重复元素的地方

   public static int rank(int key, int[] a) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (key > a[mid]) {
                lo = mid + 1;
            } else if (key < a[mid]) {
                hi = mid - 1;
            } else {

      //注意这里的mid--,这里要移动到第一个重复元素的地方。目的是为了下一步统计重复元素的个数。因为当前mid所处的位置可能是重复元素的中间
                while (a[mid - 1] == a[mid] && mid > 0)
                    mid--;
                return mid;
            }
        }
        return -1;
    }

统计元素重复的个数

  public static int count(int key, int[] a) {
        int cnt = 0;
        int i = rank(key, a);

       //注意这里i++,上面数组刚好移动到重复元素起始的位置
        while (a[i + 1] == a[i] && i < a.length) {
            cnt++;
            i++;
        }
        return cnt;
    }

移除重复的元素

public static int[] remove(int[] a, int cnt) {
        int s = 0;
        int[] b = new int[a.length - cnt];
        b[0] = a[0];
        for (int i = 0; i < a.length - 1; i++) {

     //数组在有序的情况下,通过遍历a[i]和a[i+1]就可以判断出是否有重复的元素。
            if (a[i] == a[i + 1]) {
                s++;

     //s++当前元素重复的个数
            } else {
                b[i - s + 1] = a[i + 1];
            }
        }
        return b;
    }

© 著作权归作者所有

共有 人打赏支持
gaomq
粉丝 2
博文 53
码字总数 22928
作品 0
沈阳
程序员
Java Collection 【对抗遗忘系列】 - 对Collection不断的梳理

Java2的集合框架,抽其核心,主要有三种:List、Set和Map。如下图所示: 需要注意的是,这里的 Collection、List、Set和Map都是接口(Interface),不是具体的类实现。 List lst = new Array...

止静 ⋅ 2014/09/19 ⋅ 1

Collection:List、SetMap:HashMap、HashTable

基础知识 在 Java2中,有一套设计优良的接口和类组成了Java集合框架Collection,使程序员操作成批的数据或对象元素极为方便。这些接口和类有很多对抽象数据类型操作的API,而这是我们常用的且...

颖辉小居 ⋅ 2016/01/29 ⋅ 0

算法——顺序查找和二分查找

顺序查找(无序链表): 符号表中使用的数据结构的一个简单选择就是链表,每个结点存储一个键值对。get()方法和put()方法的实现即为遍历链表。代码实现如下: 性能分析: 在表中查找一个不存...

嘿胖丁 ⋅ 03/08 ⋅ 0

HashMap和Hashtable的区别。

1 HashMap不是线程安全的 hastmap是一个接口 是map接口的实现类,是将键映射到值的对象,其中键和值都是对象,并且不能包含重复键,但可以包含重复值。HashMap允许null key和null value,而h...

零度的魚 ⋅ 2014/01/01 ⋅ 0

javase 复习汇总二:hashtable和hashmap 的区别

1 HashMap不是线程安全的 hastmap是一个接口 是map接口的子接口,是将键映射到值的对象,其中键和值都是对象,并且不能包含重复键,但可以包含重复值。HashMap允许null key和null value,而h...

yiguangtia ⋅ 2014/04/12 ⋅ 0

HashMap与HashTable区别

1 HashMap不是线程安全的 hastmap是一个接口 是map接口的子接口,是将键映射到值的对象,其中键和值都是对象,并且不能包含重复键,但可以包含重复值。HashMap允许null key和null value,而h...

闵开慧 ⋅ 2012/09/20 ⋅ 0

数据结构与算法--排序之冒泡、选择、插入、希尔

数据结构与算法--排序之冒泡、选择、插入、希尔 我们关注的主要对象是重新排列数组元素的算法,每个元素都有一个主键,排序算法的目的是将所有元素按照某种方式排列,排列后索引大的元素的主...

sunhaiyu ⋅ 2017/10/27 ⋅ 0

算法——几种查找算法的比较和应用

几种基础查找方法的性能比较: 算法(数据结构) 查找(最坏) 插入(最坏) 查找命中(平均) 插入(平均) 插入(平均)是否支持有序性相关操作 顺序查询(无序联播) N N N/2 N 否 二分查...

努力学习ding ⋅ 03/08 ⋅ 0

数据结构(集合和数组)

在使用JAVA的时候经常用到集合类(有时也称容器类),下面对常用的容器类进行一下总结。首先看一张图,了解一下集合类的结构以及他们之间的关系: 一、Collection接口 Collection接口是 Set 、...

微尘鉴 ⋅ 2016/02/22 ⋅ 0

常用查找算法及实现

一、顺序查找 线性查找是在一个已知无(或有序)序队列中找出与给定关键字相同的数的具体位置。原理是 让关键字与队列中的数从最后一个开始逐个比较,直到找出与给定关键字相同的数为止,它的...

thanatos_y ⋅ 2016/08/01 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

聊聊spring cloud的RequestRateLimiterGatewayFilter

序 本文主要研究一下spring cloud的RequestRateLimiterGatewayFilter GatewayAutoConfiguration @Configuration@ConditionalOnProperty(name = "spring.cloud.gateway.enabled", matchIfMi......

go4it ⋅ 42分钟前 ⋅ 0

Spring JavaConfig 注解

JavaConfig注解允许开发者将Bean的定义和配置放在Java类中。它是除使用XML文件定义和配置Bean外的另一种方案。 配置: 如一个Bean如果在XML文件可以这样配置: <bean id="helloBean" class="...

霍淇滨 ⋅ 50分钟前 ⋅ 0

Spring clound 组件

Spring Cloud技术应用从场景上可以分为两大类:润物无声类和独挑大梁类。 润物无声,融合在每个微服务中、依赖其它组件并为其提供服务。 Ribbon,客户端负载均衡,特性有区域亲和、重试机制。...

英雄有梦没死就别停 ⋅ 51分钟前 ⋅ 0

Confluence 6 重新获得站点备份文件

Confluence 将会创建备份,同时压缩 XML 文件后存储熬你的 <home-directory>/backups> 目录中。你需要自己访问你安装的 Confluence 服务器,并且从服务器上获得这个文件。 运行从 Confluence...

honeymose ⋅ 56分钟前 ⋅ 0

informix的常用SQL语句

1、创建数据库 eg1. 创建不记录日志的库testdb,参考语句如下: CREATE DATABASE testdb; eg2. 创建带缓冲式的记录日志的数据库testdb(SQL语句不一定在事务之中,拥有者名字不被用于对象的解...

wangxuwei ⋅ 今天 ⋅ 0

matplotlib画图

最简单的入门是从类 MATLAB API 开始,它被设计成兼容 MATLAB 绘图函数。 from pylab import *from numpy import *x = linspace(0, 5, 10)y = x ** 2figure()plot(x, y, 'r')...

Dr_hu ⋅ 今天 ⋅ 0

RabbitMQ学习以及与Spring的集成(三)

本文介绍RabbitMQ与Spring的简单集成以及消息的发送和接收。 在RabbitMQ的Spring配置文件中,首先需要增加命名空间。 xmlns:rabbit="http://www.springframework.org/schema/rabbit" 其次是模...

onedotdot ⋅ 今天 ⋅ 0

JAVA实现仿微信红包分配规则

最近过年发红包拜年成为一种新的潮流,作为程序猿对算法的好奇远远要大于对红包的好奇,这里介绍一种自己想到的一种随机红包分配策略,还请大家多多指教。 算法介绍 一、红包金额限制 对于微...

小致dad ⋅ 今天 ⋅ 0

Python 数电表格格式化 xlutils xlwt xlrd的使用

需要安装 xlutils xlwt xlrd 格式化前 格式化后 代码 先copy读取的表格,然后按照一定的规则修改,将昵称中的学号提取出来替换昵称即可 from xlrd import open_workbookfrom xlutils.copy ...

阿豪boy ⋅ 今天 ⋅ 0

面试题:使用rand5()生成rand7()

前言 读研究生这3 年,思维与本科相比变化挺大的,这几年除了看论文、设计方案,更重要的是学会注重先思考、再实现,感觉更加成熟吧,不再像个小P孩,人年轻时总会心高气傲。有1 道面试题:给...

初雪之音 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部