0

我正在尝试在一个包中实现一个名为 mostFrequent 的方法，该方法在一个包中查找最频繁的对象例如，如果 B = {Bob, Joe, Bob, Ned, Bob, Bob}，则该方法返回 Bob。提示：方法是 O(n^2)。

public E MostFrequent (Bag<E> B){ 
// implementation here
}

包的adt如下：

package edu.uprm.ece.icom4035.bag;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class StaticBag implements Bag {

    private int currentSize;

    private Object elements[];

    private class BagIterator implements Iterator {

        private int currentPosition;

        public BagIterator(){
            this.currentPosition = 0;
        }

        @Override
        public boolean hasNext() {
            return this.currentPosition < currentSize;
        }

        @Override
        public Object next() {
            if (hasNext()){
                return elements[this.currentPosition++];
            }
            else {
                throw new NoSuchElementException();
            }
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

    }

    public StaticBag(int maxSize){
        if (maxSize < 1){
            throw new IllegalArgumentException("Max size must be at least 1.");
        }

        this.currentSize = 0;
        this.elements = new Object[maxSize];
    }

    @Override
    public void add(Object obj) {
        if (obj == null){
            throw new IllegalArgumentException("Value cannot be null.");
        }
        else if (this.size() == this.elements.length){
            throw new IllegalStateException("Bag is full.");
        }
        else {
            this.elements[this.currentSize++] = obj;
        }
    }

    @Override
    public boolean erase(Object obj) {
        int target = -1;
        for (int i=0; i < this.size(); ++i){
            if (this.elements[i].equals(obj)){
                target = i;
                break;
            }
        }
        if (target == -1){
            return false;
        }
        else {
            this.elements[target] = this.elements[this.currentSize-1];
            this.elements[this.currentSize-1] = null;
            this.currentSize--;
            return true;
        }


    }

    @Override
    public int eraseAll(Object obj) {
        int copies = 0;
        while(this.erase(obj)){
            copies++;
        }

        return copies;
    }

    @Override
    public int count(Object obj) {
        int counter = 0;
        for (int i=0; i < this.size(); ++i){
            if (elements[i].equals(obj)){
                counter++;
            }
        }
        return counter;
    }

    @Override
    public void clear() {
        for (int i=0; i < this.size(); ++i){
            this.elements[i] = null;
        }
        this.currentSize = 0;
    }

    @Override
    public boolean isEmpty() {
        return this.size() == 0;
    }

    @Override
    public int size() {
        return this.currentSize;
    }

    @Override
    public boolean isMember(Object obj) {
        return this.count(obj) > 0;
    }

    @Override
    public Iterator iterator() {
        return new BagIterator();
    }

}

该方法必须以最有效的方式实施，如果可能的话，使用袋子adt中已经给出的方法

我一直在尝试的是以下内容：

public E MostFrequent(Bag<E> B){
    for(E e : B){
        int counter = B.count(e)

    }
}

但我似乎没有想到一种方法可以在循环内返回具有更多频率的对象

4

0 回答 0