1

嗨，我是新手，我不知道如何继续分析我自己完成的算法，我现在的结论是：

T(n) ϵ Ω(2n+1)
     ϵ O(2n+max)

S(n) ϵ Θ(max)

  • 'max' -> 数组中的最大整数值。

  • 'n' -> 是输入大小，即数组的长度。

这个分析正确吗？'max'会让它变成线性的吗？我怎样才能更好地表达这一点？

谢谢您的帮助。

代码

/**
 * Method findUnique2
 * 
 * Finds the unique number inside an array of integers
 * in which there are always 1 unique number and the rest
 * are repeated exactly twice.
 * 
 * NOTE:
 *  This implementation only works with positive integer numbers.
 * 
 * @param v     -> Array with the integer numbers.
 * @return      The unique number.
 */
public static int findUnique2(int[] v)
{
    int max = getMax(v);                                    // Get the maximum number
    int[] repetitions = new int[max+1];                     
    boolean found = false;
    
    // +1 to every position
    for(int i=0; i<v.length; i++)
        repetitions[v[i]]++;
    
    /*
     * Finally traversing the array an the position with
     * a 1 is the unique number the rest can be either 0
     * of not used or 2 which is a repeated number.
     */
    int i = -1;
    while(!found)
    {
        i++;
        if(repetitions[i] == 1)
            found = true;
    }
        
    return i;
}

/**
 * Method getMax
 * 
 * Traverse an array of integers and returns the maximum 
 * number stored inside it.
 * 
 * @param v An array of integers
 * @return  the maximum number among the given array.
 */
public static int getMax(int[] v)
{
    int max = v[0];
    
    for(int i=1; i<v.length; i++)
        if (max < v[i])
            max = v[i];
    
    return max;
}
4

0 回答 0