算法:有序数组删除重复元素,和查找等值键的问题
博客专区 > gaomq 的博客 > 博客详情
算法:有序数组删除重复元素,和查找等值键的问题
gaomq 发表于6个月前
算法:有序数组删除重复元素,和查找等值键的问题
  • 发表于 6个月前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

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

递归实现

 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;
    }

标签: 数据结构
共有 人打赏支持
粉丝 0
博文 37
码字总数 15024
×
gaomq
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: