@rg070836rg 2015-10-08T16:11:37.000000Z 字数 5730 阅读 1999

算法概论作业9.21

算法概论作业

2.14

给定一个含有n个元素的数组，注意到数组中的某些元素是重复的，即这些元素在数组中出现不止一次。给出一种算法，以O（nlogn）时间移除掉数组中的所有重复元素。

思路1：

先采用nlogn级别的排序算法，再线性扫描，得到结果。

package homework_chen;
/**
 * 文 件 名 : test214.java 
 * 创 建 人： chen19130216 
 * 日 期： 2015年9月21日 
 * 描 述： 算法概论2.14题目源码
 */
public class test214 {
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] r = { 8, 6, 8, 0, 4, 2, 6, 8, 3, 2, 6, 2, 1, 2, 5, 8, 0, 6, 3, 1,
                2, 3, 5, 7, 9, 5, 8, 4, 8, 5, 7, 5, 6, 6, 3, 5, };
        System.out.println("排序前：");
        printarray(r);
        System.out.println("\n排序后");
        Merge_sort(r, 0, r.length - 1);
        printarray(r);
        removerepeat(r);
    }
    public static void printarray(int[] r) {
        for (int key : r)
            System.out.print(key + " ");
    }
    /**
     * @param int []r 要求在线性时间内删除有序序列的重复元素
     */
    public static void removerepeat(int[] r) {
        int[] tmp = new int[r.length];// 大小定义比较麻烦？不知道怎么定义大小？C++可以通过传递数组长度来约束，难道java也需要么？
        int k = 0;
        int t = Integer.MIN_VALUE;
        for (int i = 0; i < r.length; i++) {// 当不一样就加进去，前提是有序序列
            if (r[i] != t) {
                tmp[k++] = r[i];
                t = r[i];
            }
        }
        System.out.println("\n删除后：");// 输出结果，有必要可以在重建大小为k的数组，重新赋值并传出去
        for (int i = 0; i < k; i++)
            System.out.print(tmp[i] + " ");
    }
    /**
     * @param int []r int start int mid int end 合并两段有序数组
     * 在调用时开辟新空间，归并，最后赋值回来，java自带gc，无须回收
     */
    public static void merge(int[] r, int start, int mid, int end) {
        int[] tmp = new int[end - start + 1];// 创建临时空间
        int k1 = start;// 记录第一有序序列的起始位置，
        int k2 = mid + 1;// 记录第一有序序列的起始位置，
        int k3 = 0;// 定义临时空间的起始位置
        while (k1 <= mid && k2 <= end) {// 当序列未到结尾时，归并
            if (r[k1] <= r[k2])// 若果第一个序列的值小于等于第二个，则把其存进临时数组
                tmp[k3++] = r[k1++];
            else
                tmp[k3++] = r[k2++];
        }
        // 当不满足while条件时，退出循环，此时将剩下的附在后面
        while (k1 <= mid)
            tmp[k3++] = r[k1++];
        while (k2 <= end)
            tmp[k3++] = r[k2++];
        // 全部完毕之后，将tmp回写到r数组中
        for (int i = 0; i < tmp.length; i++) {
            r[start++] = tmp[i];
        }
    }
    /**
     * @param int []r int start int end 归并排序数组 当start < end 分割 分割完毕之后，相邻的合并
     */
    public static void Merge_sort(int[] r, int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            Merge_sort(r, start, mid);
            Merge_sort(r, mid + 1, end);
            merge(r, start, mid, end);
        }
    }
}

思路2：

线性下找到数组的最大值，最小值，若相差距离可以接受，则此方法效率不错。然后建立hash数组，扫描r数组，若flag位置的值为false，则改为true，否则不变，最后再顺序扫描一遍hash数组，输出结果。
此方法为O（n）线性级别，不符合题目的要求，但优于题目的要求。
但适用条件为密集数组，若前后跨距太大，则得不偿失

package homework_chen;
/**
 * 文 件 名 : test214.java 
 * 创 建 人： chen19130216 
 * 日 期： 2015年9月22日 
 * 描 述： 算法概论2.14题目源码new
 */
public class test214new {
    private static int max = Integer.MAX_VALUE;
    private static int min = Integer.MIN_VALUE;
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] r = { 8, 6,  8, 0, 4, 2, 6, 8, 3, 2, 6, 2, 1, 2, 5, 8,
                0, 6, 3, 1, 2, 3, 5, 7, 9, 5, 8, 4, 8, 5, 7, 5, 6, 6, 3, 5, };
        fd_max_min(r);
        removerepeat(r, max, min);
    }
    /**
     * @param int []r 找出r数组中的最大值，最小值，并赋值给全局变量
     */
    public static void fd_max_min(int[] r) {
        for (int i = 0; i < r.length; i++) {
            if (r[i] > min)
                min = r[i];
            if (r[i] < max)
                max = r[i];
        }
        int t = min;
        min = max;
        max = t;// 交换
    }
    /**
     * @param int []r 打印数组
     */
    public static void printarray(int[] r) {
        for (int key : r)
            System.out.print(key + " ");
    }
    /**
     * 
     * @param r
     * @param max
     * @param min
     * 用hash数组判定是否存在
     */
    public static void removerepeat(int[] r, int max, int min) {
        int number = max - min + 1;
        boolean[] flag = new boolean[number];// 初始化为false
        for (int i = 0; i < r.length; i++) {
            int t = r[i] - min;
            if (flag[t] == false) {
                flag[t] = true;
            }
        }
        for (int i = 0; i < flag.length; i++) {
            if (flag[i] == true) {
                System.out.print((i + min)+" ");
            }
        }
    }
}

2.16

给定一个无穷数组A[·]，其中前N个元素都是整数，且已排好序，剩余元素均为∞。n的值未知.给出一个算法，以一个整数x为输入，以O(logn)时间找到数组中的一个位置，并满足其上的元素为x.

思路：

从a[1]开始，依次访问a[2],a[4],a[8],依次类推，访问至a[ $2^i$ ]，发现a[ $2^i$ *2]为∞，这个花费的时间代价为O(logn)
设k小于i+1, x必定在a[ $2^k$ ]至a[ $2^k$ *2]之间
对这个区间进行二分搜索，定位即可，若搜索到，返回位置，若搜索不到，返回-1.

package homework_chen;
/**
 * 文 件 名 : test216.java 
 * 创 建 人： chen19130216 
 * 日 期： 2015年9月22日 
 * 描 述： 算法概论2.16题目源码
 */
public class test216 {
    /**
     * @param args
     * 从a[1]开始，依次访问a[2],a[4],a[8], 依次类推，访问至a[2^i]，发现a[2^(i+1)]为∞，
     * 这个花费的时间代价为O(logn) 设k小于i+1, x必定在a[2^k]至a[2^(k+1)]之间
     * 对这个区间进行二分搜索， 定位即可，若搜索到，返回位置，若搜索不到，返回-1.
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] r = { 1, 2, 5, 9, 11, 15, 17, 19, 23, 27, 29, 32, 37, 41, 45, 49,
                54, 57, 59 };
        int x = 60;
        int index = solution(r, x);
        System.out.println("index:" + index);
    }
    /**
     * @param r 
     * @param x  
     * @return index 存在返回下标，不存在返回-1
     */
    private static int solution(int[] r, int x) {
        int left = 1;
        int right = 1;
        // 定位x的位置
        try {
            while (r[left] < x) {// 当x大于左界值，left翻倍
                left *= 2;
            }// 此时，数组未越界，将其作为右边界
        } catch (ArrayIndexOutOfBoundsException e) {
        } finally {
            right = left;// 此时left已经越界，将其作为右边界
            left = right / 2;
            System.out.println(left + " " + right);
        }
        int index = binSearch(r, left, right, x);
        return index;
    }
    /**
     * @param r
     * @param left
     * @param right
     * @param x
     * @return
     * 二分查找,存在返回index，不存在返回-1
     */
    private static int binSearch(int[] r, int left, int right, int x) {
        while (left <= right) {
            int mid = (left + right) / 2;
            try {
                if (x < r[mid]) {
                    right = mid - 1;
                } else if (x > r[mid]) {
                    left = mid + 1;
                } else if (x == r[mid]) {
                    return mid;
                }
            } catch (ArrayIndexOutOfBoundsException e) {
                right = mid - 1;
            }
        }
        return -1;
    }
}

2.23

如果一个数组A[1,...,n]中总数超过半数的元素都相同时，该数组被称为含有一个主元素，给定一个数组，设计一个有效算法，确定该数组中是否含有一个主元素，如果有，找出这个元素。需注意的是，该数组的元素之间可能不存在顺序——即不能进行”A[i]<A[j]”的判断，但是可以进行是否相等的判断。

思路：

整体采用分治法
当分到只有一个元素时，必定是主元素
对于连续的两段，取得左半边的主元素，取得右半边的主元素
如果左右两边一样，必定为主元素
否则线性扫描，统计次数，找到主元素，若没有返回null

package homework_chen;
/**
 * 文 件 名 : test223a.java 
 * 创 建 人： chen19130216 
 * 日 期： 2015年9月22日 
 * 描 述： 算法概论2.23题目源码
 */
public class test223a {
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] r = { 1, 1, 2, 2, 2, 3, 3, 3 };
        Integer majority = getmajority(r, 0, r.length - 1);
        System.out.println("主元素为:" + majority);
    }
    /**
     * 求数组的主元素
     * @param r
     * @param start
     * @param end
     * @return
     */
    private static Integer getmajority(int[] r, int start, int end) {
        if (start == end) {// 只有一个元素时，必定是主元素
            return r[start];
        }
        int mid = (start + end) / 2;
        Integer majority0 = getmajority(r, start, mid);// 取得左半边的主元素
        Integer majority1 = getmajority(r, mid + 1, end);// 取得右半边的主元素
        if (majority0 == majority1) {// 如果左右两边一样，必定为主元素
            return majority0;
        }
        Integer majority = traverseAndFind(r, majority0, majority1, start, end);// 综合两边主元素判定综合主元素
        return majority;
    }
    /**
     * 本方法用于返回相邻两段的主元素，若不存在，返回null
     * @param r
     * @param majority0
     * @param majority1
     * @param start
     * @param end
     * @return
     */
    private static Integer traverseAndFind(int[] r, Integer majority0,
            Integer majority1, int start, int end) {
        int halfRate = (end - start + 1) / 2;//测定程序中的半数
        int fre0 = 0;//统计次数1
        int fre1 = 0;//统计次数2
        for (int i = start; i <= end; i++) {
            if (majority0 != null && r[i] == majority0)
                fre0++;
            if (majority1 != null && r[i] == majority1)
                fre1++;
        }
        if (fre0 > halfRate)//超过半数，满足主元素条件返回
            return majority0;
        if (fre1 > halfRate)
            return majority1;
        return null;//无主元素，返回空指针
    }
}