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

typecodes

发布于 2024-03-29 14:37:10

4940

文章被收录于专栏：typecodestypecodes

遇到一个题，大概要求是写一个函数处理来去掉一个无序的整型数组（例如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_arr126 = { 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_arr226 = { 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_ar2r26 = { 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_ar3r26 = { 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( arrayi == arrayi_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_del1i_f_del1_len++ = arrayi; } ++i; } #if 1 for( i=0; i<i_f_del1_len; i++ ) { PRINT( "i_f_del1%d=%d.", i, i_f_del1i ); } #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_del2i == i_f_del2j ) { for( k=j+1; k < len; ++k ) { i_f_del2k-1 = i_f_del2k; //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_del2i ); } #endif return len; }