关于《算法》中JAVA动态调整数组的问题

    private Item[] a = (Item[]) new Object[1];
    private int N = 0;

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    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 void push(Item item) {
        //判断当数组元素计数变量N与数组的长度相等的时候 那么将数组的长度扩充2倍
        if (N == a.length) {
            resize(2 * a.length);
        }
        a[N++] = item;
    }

    public Item pop() {
        Item item = a[N--];
        a[N] = null;
        if (N > 0 && N == a.length / 4) {
            resize(a.length / 2);
        }
        return item;
    }

有朋友可以帮忙解释一下么 N > 0 && N == a.length / 4 这个条件从何而来?

吃鸡游戏
浏览 253回答 2
2回答

尚方宝剑之说

if (N > 0 && N == a.length / 4) 这是用来控制何时触发 resize 的,当不停的弹出元素时,a数组中的有效元素个数会不停的减少,此时a数组的长度是不变的,当有效元素个数 == 数组长度的4分之一时,就调整数组的长度,将其长度变为1/2

aluckdog

这是根据经验得到的。当数组小于1/4的时候,就很大概率它不会再扩充到1/2了,所以就缩小一半(在pop里)。当数组大于1/2的时候,它就有很大概率会继续扩展,那么就扩大一倍(在push里)。这么做,是权衡了空间和时间得到的相对比较优的平衡。
打开App,查看更多内容
随时随地看视频慕课网APP