TypeCodes

C语言删除无序整型数组中的重复元素及时间复杂度

遇到一个题,大概要求是写一个函数处理来去掉一个无序的整型数组(例如int i_arr[] = { 1, 2, 2, 3, 4, 2, 3, 5 };)中重复的元素,并返回最终的长度。

1 思路

看到这道题的时候,第一反应就是需要删除元素,然后联想到单链表。但是后面一想还是不划算,因为单链表还得先把数组中的元素遍历到链表节点中。

换一下思路,可以先创建另一个整型数组(大小和原数组一样),然后正向遍历数组中的元素,比较当前元素和它前面所有的元素是否重复,如果这个整数之前没有出现过,那么就放到新的数组中,于是有了小节2中的Method1;另外一种就是不需要创建新的数组,在正向遍历数组中的元素时,比较当前元素和它后面所有的元素是否重复,如果重复就把后面的所有元素向前移动(即覆盖),于是有了小节2中的Method2。

2 完整程序

程序中第104行的--j语句非常重要,这是为了避免当前元素连续出现3次(或以上)而没有被删除。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/**
 * @FileName    int_del_repeat.c
 * @Describe    A simple example for deleting the repeated elements in a deldisor interger array.
 * @Author      vfhky 2016-03-23 22:44 https://typecodes.com/cseries/deldisorderintarrrepeatele.html
 * @Compile     gcc int_del_repeat.c -o int_del_repeat
 */
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include "print.h"

int f_del1( int *i, int iLen );
int f_del2( int *i_f_del2, int len );

int main( int argc, char **argv )
{
    //The test array.
    int i_arr1[26] = { 1, 3, 2, 1, 2, 3, 4, 5, 5, 6, 7, 8, 12, 11, 22, 3, 7, 5, 13, 4, 5, 8, 7, 6, 23, 12 };
    int i_arr2[26] = { 1, 3, 2, 1, 2, 3, 4, 5, 5, 6, 7, 8, 12, 11, 22, 3, 7, 5, 13, 4, 5, 8, 7, 6, 23, 12 };
    int i_ar2r[26] = { 1, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 8, 11, 11, 12, 13, 13, 13, 13, 14, 15, 15, 17, 18, 23, 24 };
    int i_ar3r[26] = { 1, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 8, 11, 11, 12, 13, 13, 13, 13, 14, 15, 15, 17, 18, 23, 24 };

    //The length of .
    int i_p_len = 0;

    #if 1
    i_p_len = f_del1( i_ar2r, 26 );
    PRINT( "len=[%d].", i_p_len );
    #endif

    PRINT( "------------------------------\n" );

    #if 1
    i_p_len = f_del2( i_ar3r, 26 );
    PRINT( "len=[%d].", i_p_len );
    #endif

    return 0;
}

//Method 1: Using malloc to init an array for storing the elements after deleting the repeated ones.
int f_del1( int *array, int iLen )
{
    int i = 1;
    int i_recycle = 0;
    //Flags to store an element into the array i_f_del1.
    int i_flag = 1;
    //Length of the sorted array, name as i_f_del1.
    int i_f_del1_len = 1;

    //Init an array for storing the elements after deleting the repeated ones.
    int *i_f_del1 = (int *)malloc( iLen*sizeof(int) );
    //Init the first interger element.
    *i_f_del1 = *array;

    while( i < iLen )
    {
        i_flag = 1;
        i_recycle = 0;
        while( i_recycle < i )
        {
            if( array[i] == array[i_recycle++] )
            {
                i_flag = 0;
                break;
            }
        }

        //If i_flag equals 1, we should put the current element to the array i_f_del1.
        if( i_flag )
        {
            i_f_del1[i_f_del1_len++] = array[i];
        }

        ++i;
    }

#if 1
    for( i=0; i<i_f_del1_len; i++ )
    {
        PRINT( "i_f_del1[%d]=[%d].", i, i_f_del1[i] );
    }
#endif

    return i_f_del1_len;
}

//Method 2: cover up the repeated elements.
int f_del2( int *i_f_del2, int len )
{
    int i = 0, j = 0, k = 0;
    for( i=0; i<len; i++ )
    {
        for( j=i+1; j<len; j++ )
        {
            if( i_f_del2[i] == i_f_del2[j] )
            {
                for( k=j+1; k < len; ++k )
                {
                    i_f_del2[k-1] = i_f_del2[k];        //cover up
                }
                --len;
                //Key step to avoiding the continuous elements repeated more than 2 times.
                --j;
            }
        }
    }

    #if 1
    for( i=0; i<len; ++i )
    {
        PRINT( "i_f_del2[%d]=[%d].", i, i_f_del2[i] );
    }
    #endif

    return len;
}

3 测试执行

使用《Linux C/C++工程中可生成ELF、动/静态库文件的通用Makefile》一文中的Makefile文件进行程序编译,当然也可以使用命令进行编译gcc int_del_repeat.c -o int_del_repeat

C语言删除无序整型数组中的重复元素

4 时间复杂度

Method 2中的时间复杂度为O(N^2),Method 2中的时间复杂度为O(N^3)。

Comments »