文档章节

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

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

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

止静
2014/09/19
0
1
Collection:List、SetMap:HashMap、HashTable

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

颖辉小居
2016/01/29
5
0
HashMap和Hashtable的区别。

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

零度的魚
2014/01/01
0
0
算法——顺序查找和二分查找

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

嘿胖丁
03/08
4
0
javase 复习汇总二:hashtable和hashmap 的区别

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

yiguangtia
2014/04/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

spring 事件

ContextRefreshedEvent Event raised when an {@code ApplicationContext} gets initialized or refreshed. ContextClosedEvent Event raised when an {@code ApplicationContext} gets clos......

Canaan_
33分钟前
1
0
leetcode两数之和

leetcode中求两数之和解决方法 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 给定 nums = [2, 7, 11, ...

lar555
49分钟前
1
0
js实现限制网页内容复制

转载 在我们做的网页发到网上后,如果访客看到比较喜欢的内容,只要复制就可以变为自己的,自己辛辛苦苦弄半天还不及人家的一下复制,有时为了只让访客看到,而不能让它们复制内容,就用Jav...

lc_comeon
54分钟前
1
0
jenkins将spring boot项目发布到阿里云镜像中

1、spring boot项目 1.1 pom.xml配置 <artifactId>xxx-docker</artifactId><properties><project.build.sourceEncoding>UTF-8</project.build.sourceEncoding><project.reporting.......

xixingzhe
今天
0
0
qsv格式可以在电视上播放吗

  大家都知道qsv格式是爱奇艺的独家缓存格式,是加密的,一般的播放器是无法播放的,只能在爱奇艺播放器上播放,如果想要在电视上播放,就必须要安装爱奇艺播放器,比较麻烦。其实还有一种...

萤火的萤火
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部