文档章节

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

gaomq
 gaomq
发布于 2017/06/03 14:30
字数 492
阅读 15
收藏 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
博文 59
码字总数 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
算法——顺序查找和二分查找

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

嘿胖丁
03/08
4
0
HashMap与HashTable区别

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

闵开慧
2012/09/20
0
0
HashMap和Hashtable的区别。

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

零度的魚
2014/01/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

根据进程名称杀死进程

ps -ef | grep keyword | grep -v grep | awk '{print $2}' | xargs kill -9 逐个分析: 1, ps -ef | grep keyword: 查出进程名含有 keyword 的所有进程; 2, grep -v grep: 从这些结果里面,把......

vinci321
20分钟前
0
0
nginx的简单使用:负载均衡

nginx:反向代理的服务器;用户发送请求到nginx,nginx把请求发送给真正的服务器,等待服务器处理完数据并返回,再把数据发送给用户。 nginx作为一个反向代理服务器,能缓存我们项目的静态文...

osliang
36分钟前
2
0
网站title标题被改并被百度网址安全中心提醒的解决办法

国庆假日期间我们Sine安全接到众多网站站长求助网站标题被改导致在百度搜索中百度安全中心提醒被拦截,导致网站正常用户无法浏览网站被跳转到一些菠菜du博网站,而且很明显的一个特征就是在百...

网站安全
38分钟前
1
0
JDK版本与major.minor version的对照关系

其实,只需要记住jdk6对于major.minor version 50即可,其他版本自行计算即可。 ---------------------

码代码的小司机
40分钟前
1
0
C++基础教程面向对象学习笔记及心得感悟[图]

C++基础教程面向对象学习笔记及心得感悟[图] 使用友元函数重载算术运算符: C ++中一些最常用的运算符是算术运算符 - 即加号运算符(+),减运算符( - ),乘法运算符(*)和除法运算符(/...

原创小博客
48分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部