1### 2. L = (a,b,c,d,e) ... 做图

初始状态:

0 1 2 3 4 5 6 7 8 9
a b c d e  

insert(0,f)

0 1 2 3 4 5 6 7 8 9
f a b c d e  

insert(3,g)

0 1 2 3 4 5 6 7 8 9
f a b g c d e  

insert(7,h)

0 1 2 3 4 5 6 7 8 9
f a b g c d e h  

earse(0)

0 1 2 3 4 5 6 7 8 9
a b g c d e h  

erase(4)

0 1 2 3 4 5 6 7 8 9
a b g c e h  

3. changeLength2D

二维数组的话要基于Array设计一个矩阵类，其中的每一行都是一个Array对象。

template <class T>
class ArrayMatrix: public Array{
    void changeLength2D( int x, int len );
}

template <class T>
void ArrayMatrix::changeLength2D( int rowIndex, int len ){
    checkIndex(x);
    get(rowIndex).changeLength(len);
}

3. 构造函数

好像题目描述有问题。 我自己写的是提供一个是否自动扩容的参数。如果配置为不自动扩容则在超出的时候抛出异常。

enum class ARRAY_AUTO_CAPACITY
{
    DISABLED = 0,ENABLED = 1
};

template <class T>
class Array{
public:
    Array(int initCapacity = ARRAY_DEFAULT_CAPACITY, ARRAY_AUTO_CAPACITY autoCapacity = ARRAY_AUTO_CAPACITY::DISABLED);
    void checkMax();
private:
    ARRAY_AUTO_CAPACITY _autoCapacity =  ARRAY_AUTO_CAPACITY::DISABLED;
}


template<class T>
inline void Array<T>::checkMax()
{
    if (_size >= _capacity) {

        switch (_autoCapcity)
        {
        case ARRAY_AUTO_CAPACITY::ENABLED:
            changeCapacityTo(_capacity << 1);
            break;
        case ARRAY_AUTO_CAPACITY::DISABLED:
            throw illegalInputData("Array is full.");
            break;
        default:
            break;
        }
    }
}

5. trimToSize()

实际上就是改变数组长度， 长度为size或1。 这里我基于我改写的 changeCapacityTo()来实现，实际上是一回事。

复杂度是O(n)

void trimToSize(){
    changeCapacityTo( _size>0 ? _size : 1 );
}

template<class T>
inline void Array<T>::changeCapacityTo(int newCapacity)
{
    T* newElements = new T[newCapacity];
    _capacity = newCapacity;
    _size = newCapacity < _size ? newCapacity : _size;

    for (int i = 0; i < _size; i++)
    {
        newElements[i] = _elements[i];
    }
    delete[] _elements;

    _elements = newElements;
}

6. setSize

这一题，同样题目描述是有问题的。 见上一题changeCapacityTo()

7. 重载[]

T& operator[]( int n){
    checkIndex(n);
    return _elements[n];
}

8. 重载==

template<class T>
bool operator==( const Array<T>& targetArray ) const{
    if( size()!= targetArray.size() ){
        return false;
    }
    for( int i=0; i<size();i++ ){
        if( get(i) != target.get(i) ){
            return false;
        }
    }
    return true;
}

9. 重载!=

template<class T>
bool operator!=( const Array<T>& targetArray ){
    return !*this == targetArray;
}

10. 重载<

见8 . 其中!= 替换为>

11. push_back

只需要考虑越界情况，其他情况均是O(1)

12. pop_back

同11

13. swap(list)

O(1) 实际上只需要交换 _elements 的地址，_size, _capacity 即可

14. reseve(theCapacity)

Ω(1) O(n)

reserve(theCapacity){
    if( theCapacity > _capacity ){
        changeCapacityTo( theCapacity );
    }
}

15. set( int theIndex, T& theElement )

void set( int theIndex, T& theElement){
    checkIndex(theIndex);
    _elements[theIndex] = theElement;
}

16. clear()

O(n) 取决于size

void clear(){
    delete[] _elements;
    _elements = new T[ARRAY_DEFAULT_CAPACITY];
    _size = 0;
}

17. removeRange()

O(n) 在局部来说复杂度比 erase 要低，但是从渐进意义上来说没有区别。 因为范围无限趋近于1，总移动步数依然趋近于n。 我在这里使用erase进行重载。


template<class T>
inline void Array<T>::erase(int n)
{
    checkIndex(n);

    while (n < _size - 1)
    {
        _elements[n] = _elements[++n];
    }
    _elements[--_size].~T(); // 只删除了一个，所以只需要将移动后的 最后元素释放 & size 自减
    checkMin();
}

template<class T>
inline void Array<T>::erase(int startIndex, int endIndex)
{
    checkIndex(startIndex);
    checkIndex(endIndex);

    int len = endIndex - startIndex + 1;
    len = len < _size - endIndex ? len : _size - endIndex;

    for (int i = 0; i < len; i++)
    {
        _elements[i + startIndex] = _elements[endIndex + i + 1];
    }
    _size -= endIndex - startIndex + 1;
    checkMin();
}

18. lastIndexOf()

O(n) 反向遍历

19. ...

20. 缩容

20.1

void chechMin(){

    if (_size < _capacity >> 2) {

        changeCapacityTo(_capacity >> 1 > ARRAY_DEFAULT_CAPACITY ? _capacity >> 1 : ARRAY_DEFAULT_CAPACITY);
    }
}

...

23. leftShift(i)

O(n)

新数组 nElements = new T[_size-i] 从i开始遍历，遍历长度为 _size -i 依次移动 _elements[i] 到 nElements[i] 即可。

24. 循环移动

24.1 不知道逆转

24.2 circularShift 这里每一步实际上都不用真正执行，假设数组长度5，移动50次的话 是不是恰好回到原位？ 所以这里只需要将移动的总步数简单运算即可得到最终的位置偏移量，即： int offset = i % _size; 循环将 第i个元素取出并替换到对应的新位置即可。 O(n)

void circularShift( int i ){

    int offset = i%_size;
    if( offset == 0) return;

    for( int k =0; k<_size; k++ ){
        swap(k, k+offset < _size ? k+offset : k+offset-_size ); 
        // 使用三元运算 考虑取模运算与比较运算的细微效率差异
        // 也可以使用 T tmp 做中转
    }
}
  1. half() O(n) O(_size/2)
void half(){
    int max = (_size+1) / 2; 取上整
    T* nElements = new T[max];
    for( int i =0; i<max; i++ ){
        nElements[i] = _elements[i*2-2];
    }
    delete[] _elements;
    _elements = nElements;
}

26. 使用get,set函数即可

27. pass

28. meld( Array a, Array b)

这题实际上就是归并排序中的归并，解法就是取较小的size，遍历并插入到新数组中。 未完成时，取较大的size并继续从较大数组中依次取出。

29. merge( Array a, Array b )

merge需要使用两个指针分别指向a，b。每次比中选择较小的那个，并将该指针自增。 如果某个数组已经遍历完成，则将另一个数组的剩余元素全部加入新的序列。

void merge( Array<T> a, Array<T> b ){

    int sizeA = a.size(), sizeB = b.size();
    int min = sizeA < sizeB ? sizeA : sizeB;

    delete[] _elements;
    _capacity = sizeA+sizeB+1;
    _elements = new T[_capacity];
    _size = 0;

    int i=0, j=0;

    while( i<min && j<min ){
        if( a.[i] > b.[j] ){
            _elements[_size++] = b[j++]
        }else{
            _elements[_size++] = a[i++];
        }
        // 可改写为
        // _elements[_size++] = a[i] > b[j] ? b[j++] : a[i++];
    }
    // 循环结束必有一个数组已全部取出

    if( i==min ){ // b尚未取完
        while( j< sizeB ){
            _elements[_size++] = b[j++];
        }
    }else{ // a尚未取完 或 都取完
        while( i< sizeA ){
            _elements[_size++] = a[i++];
        }
    }
}

30. split( a, b )

这个其实挺简单，遍历当前对象，每次自增2，这样依次处理2个元素。 之后如果是奇数，再增加一个到b中，偶数直接结束。

void split( Array a, Array b ){

    a.clear(); b.clear();

    for( int i=0; i< _size-1; i+=2 ){

        a.push( this[i+1] );
        b.push( this[i] );
        // 使用push方法向最后追加
    }
    if( size()/2 == 1 ){
        b.push( _size-1 );
    }
}

31. 可以评估动态操作时 左右移动方向的循环数组 PASS

大体思路就是进行增删的时候，判断一下左移右移的成本，然后选择一个范围和方向进行移动。

在循环数组中： 删除操作离哪边近，哪边就快。 增加的话似乎也是一样的，譬如说在0的位置增加一个，则可以将原来的0 防止到 _size处，一次操作移动完成。如果向右侧，则需要 _size次操作。

文章地址:



标签: c++, 数据结构、算法与应用

添加新评论