文档章节

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

gaomq
 gaomq
发布于 2017/06/03 14:30
字数 492
阅读 21
收藏 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
粉丝 3
博文 59
码字总数 23993
作品 0
合肥
程序员
私信 提问
Java Collection 【对抗遗忘系列】 - 对Collection不断的梳理

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

止静
2014/09/19
0
1
算法——顺序查找和二分查找

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

嘿胖丁
03/08
4
0
Collection:List、SetMap:HashMap、HashTable

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

颖辉小居
2016/01/29
5
0
数据结构与算法--排序之冒泡、选择、插入、希尔

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

sunhaiyu
2017/10/27
0
0
HashMap和Hashtable的区别。

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

零度的魚
2014/01/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

spring学习笔记(二)spring 事件的使用

spring 中的事件 spring事件通过订阅发布 可以解耦操作 可以同步 可以异步 步骤 编写事件 通过继承org.springframework.context.ApplicationEvent 来编写事件 public ApplicationEvent(Obj...

NotFound403
23分钟前
1
0
特斯拉车主成功破解了自己Model 3汽车

据汽车博客Electrek消息,一位特斯拉车主成功破解了自己Model 3汽车,还在此基础上运行了Ubuntu。 这位叫trsohmers的网友表示,“功劳大多要归到Ingineerix的头上,他花了数月才找到初始的那...

linuxCool
37分钟前
1
0
Gitbook : random errors when using gitbook plugin on running "gitbook serve"

在执行gitbook serve时,会有不定的失败错误 参考问题 :#1309 解决方案: 更新gitbook版本,这个问题似乎是3版本的问题 , 官方也不打算在这个版本解决了。 更新 到最新版本后, 不再出现问...

ol_O_O_lo
51分钟前
1
0
提灯照暗,向内自省——《中国文化的深层结构》读书笔记3800字

提灯照暗,向内自省——《中国文化的深层结构》读书笔记3800字: 作者:王健茜;断断续续一个多月才读完了《中国文化的深层结构》,这并不是一本难懂的书,之所以读得慢,源于对书中观点的思...

原创小博客
54分钟前
1
0
高德地图-行政区域接口

1、获取全国各省信息 https://restapi.amap.com/v3/config/district?extensions=all&key=应用Key&s=rsv3&output=json 2、获取下级行政区域信息 https://restapi.amap.com/v3/config/distric......

voole
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部