16. [2015年第41题]用单链表保存m个整数，结点的结构为( data, link )，且ldata|<n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。

这个问题是要对一个单链表进行操作，去除其中所有除了第一个出现的、data值绝对值相同的节点。由于题目强调了需要高效的时间复杂度，我们不能遍历整个链表两次，因为这将导致O(m^2)的时间复杂度，不符合要求。

一个更有效的方法是使用哈希集合（Hash Set），在遍历链表的过程中，遇到新的数据值，就将其添加到哈希集合中。同时，继续遍历链表，如果当前节点的数据值已经在集合中，说明这是该值的后续节点，可以跳过；如果不在集合中，表示这是第一个出现的，将其加入链表并添加到集合中，然后删除前一个节点。这样，时间复杂度可以达到O(m)，其中m是链表中的节点总数。

以下是Python伪代码示例：

def remove_duplicates(head):
    if not head or not head.next:
        return head

    seen = set()
    current = head
    while current:
        if abs(current.data) in seen:
            # 删除重复节点
            prev.next = current.next
        else:
            seen.add(abs(current.data))
            current = current.next

    return head

相关问题

优化这段代码template<typename T> class MyTemplateClass:public QObject { Q_OBJECT public: MyTemplateClass(const T& data) : m_data(data) { qRegisterMetaType<SP104>("SP104"); qRegisterMetaType<DP104>("DP104"); qRegisterMetaType<SP104_T>("SP104_T"); qRegisterMetaType<DP104_T>("DP104_T"); qRegisterMetaType<ME_NA104>("ME_NA104"); qRegisterMetaType<ME_NB104>("ME_NB104"); qRegisterMetaType<ME_NC104>("ME_NC104"); qRegisterMetaType<YK_SP104>("YK_SP104"); qRegisterMetaType<YK_DP104>("YK_DP104"); t_cache.setMaxCost(MAP_MAX); } QMap<QString,QVector<T>>t_map; QMap<QString,QVector<T>>old_map; QCache<QString,QVector<T>>t_cache; QVector<T>t_vctor; QDateTime start_time; int state_flg; int expect_timedif; void set_firstaddr(int yxaddr,int ycaddr) { m_yxAddr = static_cast<int32_t>(yxaddr); m_ycAddr= static_cast<int32_t>(ycaddr); } int32_t m_yxAddr; int32_t m_ycAddr; void set_flg(int flg) { state_flg=flg; } int get_flg() { return state_flg; } void set_expect_time(int time) { expect_timedif=time; } float GetByteToFloat(BYTE data[4]) { FloatLongType value; value.ldata = data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24); return value.fdata; } QDateTime CP56TiToQDateTi(CP56Time time) { int MillSecond = (time.wMilliSeconds[1] << 8) + time.wMilliSeconds[0]; QTime sTime(time.byHours, time.byMinutes, MillSecond / 1000, MillSecond % 1000); QDate sDate(time.byYears + 2000, time.byMonths, time.byDays); return QDateTime(sDate, sTime); } signals: void data_fit(int flg,QString name); private: T m_data; };

这段代码可以进行如下的优化：

1. 将一些注册元类型的操作放在类的构造函数外部进行，以减少每次创建类对象时的重复操作。

2. 将一些不常用的操作（如 GetByteToFloat 和 CP56TiToQDateTi 函数）移出类的定义，以减小类的体积和提高代码的可读性。

3. 将一些变量的初始化操作放在类的构造函数初始化列表中，以提高代码的效率。

下面是优化后的代码：

template<typename T> 
class MyTemplateClass: public QObject 
{     
    Q_OBJECT 
public:     
    MyTemplateClass(const T& data) : 
        QObject(nullptr), 
        m_data(data), 
        t_cache(MAP_MAX), 
        state_flg(0), 
        expect_timedif(0) 
    {         
        qRegisterMetaType<SP104>("SP104");         
        qRegisterMetaType<DP104>("DP104");         
        qRegisterMetaType<SP104_T>("SP104_T");         
        qRegisterMetaType<DP104_T>("DP104_T");         
        qRegisterMetaType<ME_NA104>("ME_NA104");         
        qRegisterMetaType<ME_NB104>("ME_NB104");         
        qRegisterMetaType<ME_NC104>("ME_NC104");         
        qRegisterMetaType<YK_SP104>("YK_SP104");         
        qRegisterMetaType<YK_DP104>("YK_DP104");     
    }     
    QMap<QString,QVector<T>> t_map;     
    QMap<QString,QVector<T>> old_map;     
    QCache<QString,QVector<T>> t_cache;     
    QVector<T> t_vctor;     
    QDateTime start_time;     
    int state_flg;     
    int expect_timedif;      
    void set_firstaddr(int yxaddr,int ycaddr)     
    {         
        m_yxAddr = static_cast<int32_t>(yxaddr);         
        m_ycAddr= static_cast<int32_t>(ycaddr);     
    }      
    int32_t m_yxAddr;     
    int32_t m_ycAddr;      
    void set_flg(int flg)     
    {         
        state_flg=flg;     
    }     
    int get_flg()     
    {         
        return state_flg;     
    }     
    void set_expect_time(int time)     
    {         
        expect_timedif=time;     
    } 
signals:         
    void data_fit(int flg,QString name); 
private:     
    T m_data; 
};

In [139]: data = pd.read_csv('examples/macrodata.csv') In [140]: data.head() Out[140]: year quarter realgdp realcons realinv realgovt realdpi cpi \ 0 1959.0 1.0 2710.349 1707.4 286.898 470.045 1886.9 28.98 1 1959.0 2.0 2778.801 1733.7 310.859 481.301 1919.7 29.15 2 1959.0 3.0 2775.488 1751.8 289.226 491.260 1916.4 29.35 3 1959.0 4.0 2785.204 1753.7 299.356 484.052 1931.3 29.37 4 1960.0 1.0 2847.699 1770.5 331.722 462.199 1955.5 29.54 m1 tbilrate unemp pop infl realint 0 139.7 2.82 5.8 177.146 0.00 0.00 1 141.7 3.08 5.1 177.830 2.34 0.74 2 140.5 3.82 5.3 178.657 2.74 1.09 3 140.0 4.33 5.6 179.386 0.27 4.06 4 139.6 3.50 5.2 180.007 2.31 1.19 In [141]: periods = pd.PeriodIndex(year=data.year, quarter=data.quarter, .....: name='date') In [142]: columns = pd.Index(['realgdp', 'infl', 'unemp'], name='item') In [143]: data = data.reindex(columns=columns) In [144]: data.index = periods.to_timestamp('D', 'end') In [145]: ldata = data.stack().reset_index().rename(columns={0: 'value'})

这段代码主要是对宏观经济数据集进行处理。具体来说，代码的主要步骤如下：

1. 首先使用 pd.read_csv() 函数读取 'examples/macrodata.csv' 文件中的数据，将其存储到 DataFrame 对象 data 中。

2. 接着，通过将 year 和 quarter 列合并为一个表示日期的 PeriodIndex 对象来重新索引 data。

3. 然后，使用 pd.Index() 函数创建包含三个元素 'realgdp'、'infl' 和 'unemp' 的 Index 对象 columns，将其命名为 'item'。

4. 接着，使用 data.reindex() 函数将 data DataFrame 的列重新索引为 columns 中包含的三个元素，并将结果存储回 data。

5. 然后，使用 pd.PeriodIndex.to_timestamp() 函数将 PeriodIndex 对象 periods 转换为时间戳索引，并将其从每个季度的最后一天转换为每个季度的末尾。

6. 最后，使用 stack() 函数将 DataFrame data 中的列转换为行，并使用 reset_index() 函数将多级行索引转换为普通 DataFrame，然后使用 rename() 函数将其唯一的列命名为 'value'，最终结果是存储在 ldata DataFrame 中。

综上所述，这段代码的主要目的是对数据进行预处理，以便后续更方便地进行数据分析和可视化。