本系列博客習(xí)題來自《算法(第四版)》，算是本人的讀書筆記，如果有人在讀這本書的，歡迎大家多多交流。為了方便討論，本人新建了一個(gè)微信群(算法交流)，想要加入的，請(qǐng)?zhí)砑游业奈⑿盘?hào)：zhujinhui207407 謝謝。另外，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論

算法(第4版)

知識(shí)點(diǎn)

• 刪除一個(gè)元素

題目

1.3.38 刪除第 k 個(gè)元素。實(shí)現(xiàn)一個(gè)類并支持下表的 API：

API for a generic generalized queue

1.3.38 Delete kth element. Implement a class that supports the following API:
First, develop an implementation that uses an array implementation, and then develop one that uses a linked-list implementation. Note: the algorithms and data structures that we introduce in Chapter 3 make it possible to develop an implementation that can guarantee that both insert() and delete() take time prortional to the logarithm of the number of items in the queue—see Exercise 3.5.27.

分析

這道題有多種解法，這里我們列舉幾種，并一一闡釋它的優(yōu)缺點(diǎn)

答案

用數(shù)組實(shí)現(xiàn)
答案一：這種解法應(yīng)該是最容易理解的，當(dāng)insert的時(shí)候就從最后插入，當(dāng)delete的時(shí)候就把數(shù)組的第K個(gè)delete，并把k后面的移到前面來。

public class GeneralizedQueue<Item> implements Iterable<Item> {

    private Item[] a;
    private int N;
    
    public GeneralizedQueue(){
        N = 0;
        a = (Item[]) new Object[1];
    }
    
    public boolean isEmpty(){
        return N == 0;
    }
    
    public void insert(Item x){
        if (N == a.length) {
            resize(N * 2);
        }
        a[N++] = x;
    }
    
    public Item delete(int k){
        if (k > N || k < 0) {
            return null;
        }
        
        if (N == a.length / 4) {
            resize(a.length / 2);
        }
        Item target = a[k];
        Item[] temp = (Item[])(new Object[N]);
        for (int i = 0; i < N; i++) {
            if (i < k) {
                temp[i] = a[i];
            }else {
                temp[i] = a[ i+ 1];
            }
            
        }
        a = temp;
        a[--N] = null;
        return target;
    }
    
    private void resize(int max){
        Item[] temp = (Item[])(new Object[max]);
        for (int i = 0; i < N; i++) {
            temp[i] = a[i];
        }
        a = temp;
    }
    
    public Iterator<Item> iterator() {
        return new GeneralizedQueueIterator();
    }
    
    public class GeneralizedQueueIterator implements Iterator<Item>{

        private Item[] temp;
        private int index ;
        
        public GeneralizedQueueIterator(){
            temp = (Item[])new Object[N];
            for (int i = 0; i < N; i++)
                temp[i] = a[i];
            
            index = 0;
        }
        
        public boolean hasNext() {
            return index < N;
        }

        public Item next() {
            return temp[index++];
        }

        public void remove() {
            
        }
        
    }
    
    public static void main(String[] args) {
        GeneralizedQueue<String> queue = new GeneralizedQueue<String>();
        queue.insert("我");
        queue.insert("的");
        queue.insert("名字");
        queue.insert("叫頂級(jí)程序員不穿女裝");
        queue.insert("微博:https://m.weibo.cn/p/1005056186766482");
        
        queue.delete(0);
        queue.delete(2);

        for (String string : queue) {
            System.out.println(string);
        }
        
    }

}

用鏈表實(shí)現(xiàn)

廣告

我的首款個(gè)人開發(fā)的APP壁紙寶貝上線了，歡迎大家下載。

壁紙寶貝