字符串数组去重的多方面阐述

一、字符串数组去重复

字符串数组去重复是指在一个字符串数组中，去掉重复的元素，使得数组中的元素唯一。字符串数组去重复是一个常见的问题，因为在实际的开发中，我们经常需要对一个字符串数组进行去重操作。下面我们就来看一下字符串数组去重的一些方法和原理。

二、字符串数组去重算法

常见的字符串数组去重算法有两种，分别是：哈希表法和双重循环法。

1、哈希表法

std::unordered_set
    unique_set;

for (auto str: str_array)
{
    unique_set.insert(str);
}

std::vector
     unique_str_array(unique_set.begin(), unique_set.end());

    
   

哈希表法的实现原理是创建一个哈希表，将字符串数组中的每个元素都插入到哈希表中。由于哈希表中不能存在相同的元素，所以最终得到的哈希表中就是去重后的字符串数组。在C++中，可以使用std::unordered_set实现哈希表。

2、双重循环法

for (int i = 0; i < str_array.size(); ++i)
{
    bool flag = false;
    for (int j = 0; j < i; ++j)
    {
        if (str_array[i] == str_array[j])
        {
            flag = true;
            break;
        }
    }
    if (flag == false)
    {
        unique_str_array.push_back(str_array[i]);
    }
}

双重循环法的实现原理是，使用两个循环遍历整个字符串数组，对于每个元素，判断它前面是否已经出现过。如果已经出现过，则标记为重复元素，否则添加到新的数组中。该方法的时间复杂度为O(N^2)。

三、字符串数组去重c语言代码

在C语言中，可以使用hash表实现字符串数组去重。

// 哈希表大小
#define HAVEHT_SIZE 100

// 哈希表结构体
typedef struct _haveht
{
    char* val;  // 值
    struct _haveht* next;   // 链表指针
} haveht;

// 哈希表
haveht* hashTable[HASH_SIZE];

void cleanHashTable()
{
    memset(hashTable, 0, sizeof(hashTable));
}

int hash(const char* str)
{
    int hash = 0;
    int len = strlen(str);

    for (int i = 0; i < len; i++)
    {
        hash = hash * 31 + str[i];
    }

    return (hash & 0x7fffffff) % HAVEHT_SIZE;
}

void addHashtable(const char* str)
{
    int key = hash(str);
    haveht* node = hashTable[key];

    while (node != NULL)
    {
        if (strcmp(node->val, str) == 0)
        {
            return;
        }
        node = node->next;
    }

    haveht* new_node = (haveht*)malloc(sizeof(haveht));
    new_node->val = str;
    new_node->next = hashTable[key];
    hashTable[key] = new_node;
}

//去重函数
int unique(char* a[], int n)
{
    cleanHashTable();

    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (strlen(a[i]) == 0)
        {
            continue;
        }

        int key = hash(a[i]);
        haveht* node = hashTable[key];

        while (node != NULL)
        {
            if (strcmp(node->val, a[i]) == 0)
            {
                a[i][0] = 0;
                break;
            }
            node = node->next;
        }

        if (strlen(a[i]) != 0)
        {
            addHashtable(a[i]);
            cnt++;
        }
    }

    return cnt;
}

四、前端字符串数组去重

在前端的开发中，我们同样需要对字符串数组进行去重。下面我们就来介绍几种前端去重的方式。

1、ES6 Set去重法

const arr = ['aaa', 'bbb', 'ccc', 'aaa', 'bbb'];

function unique(arr) {
  return [...new Set(arr)];
}

const uniqueArr = unique(arr); // ['aaa', 'bbb', 'ccc']

ES6中提供了Set数据结构，Set可以自动去重。结合ES6的解构语法，就可以使用一行代码实现字符串数组的去重操作。

2、reduce去重法

const arr = ['aaa', 'bbb', 'ccc', 'aaa', 'bbb'];

function unique(arr) {
  return arr.reduce((res, cur) => {
    return res.includes(cur) ? res : [...res, cur];
  }, []);
}

const uniqueArr = unique(arr); // ['aaa', 'bbb', 'ccc']

reduce函数是JS中非常常用的函数，通常用于将一个数组中的元素按照某种方式进行聚合。在去重时，我们可以通过reduce函数来依次遍历数组中的每个元素，将不同的元素保存到res数组中，从而实现去重操作。这种方法的时间复杂度为O(N)。

3、filter去重法

const arr = ['aaa', 'bbb', 'ccc', 'aaa', 'bbb'];

function unique(arr) {
  return arr.filter((el, index, arr) => {
    return arr.indexOf(el) === index;
  });
}

const uniqueArr = unique(arr); // ['aaa', 'bbb', 'ccc']

filter函数通常用于过滤数组中的元素，从而得到一个新的符合条件的数组。在去重时，我们可以通过filter函数来过滤掉重复的元素，从而得到一个新的数组。这种方法的时间复杂度为O(N^2)。

五、定义字符串数组

定义字符串数组，需要使用类型为char*的指针数组即可。例如，可以使用以下方式来定义一个长度为3的字符串数组：

char* str_array[3] = {"aaa", "bbb", "ccc"};

六、字符串和数组的区别

字符串和数组都是C/C++/JS中经常使用的数据结构，它们都有相似的定义和使用方式，但是它们之间存在一些区别。

1、内存存储方式不同

数组的元素是连续存储的，而字符串的元素是在内存中分散存储的。数组的元素存储在一个数据块中，通过索引可以直接访问到元素。而字符串的元素存储在不同的内存块中，需要使用指针来访问。

2、定义方式不同

在定义一个数组时，需要指定数组的大小，在定义字符串时，可以根据字符串的长度自动分配内存空间。

3、字符串具有特殊的终止符

字符串在内存中有一个特殊的终止符，即'\0'，用来标识字符串的结尾，而数组没有这个终止符。

七、字符串数组重排

字符串数组重排指的是将一个字符串数组按照指定的顺序重新排列。下面我们介绍两种常见的字符串数组重排方式。

1、快速排序法

void quickSort(char **str_array, int left, int right) 
{
    if (left >= right) {
        return;
    }

    char* pivot = *(str_array + left);
    int i = left + 1, j = right;

    while (true) 
    {
        while (i <= j && strcmp(*(str_array + i), pivot) < 0) 
        {
            i++;
        }

        while (i <= j && strcmp(*(str_array + j), pivot) >= 0) 
        {
            j--;
        }

        if (i > j) 
        {
            break;
        }

        char* temp = *(str_array + i);
        *(str_array + i) = *(str_array + j);
        *(str_array + j) = temp;
    }

    *(str_array + left) = *(str_array + j);
    *(str_array + j) = pivot;

    quickSort(str_array, left, j - 1);
    quickSort(str_array, j + 1, right);
}

快速排序法是一种高效的排序算法，时间复杂度为O(NlogN)。在对字符串数组重排时，我们可以使用快速排序法将数组中的元素按照一定的顺序进行排序。例如，下面的代码可以对字符串数组按照字典序进行排序：

char* str_array[5] = {"hello", "world", "apple", "banana", "cat"};

quickSort(str_array, 0, 4);

for (int i = 0; i < 5; ++i)
{
    printf("%s ", *(str_array + i));
}

2、STL中的sort函数

#include 
   

bool compareFunc (const char* a, const char* b) 
{ 
    return strcmp(a,b) < 0; 
}

int main() 
{
    char* str_array[5] = {"hello", "world", "apple", "banana", "cat"};

    std::sort(str_array, str_array + 5, compareFunc);

    for(int i = 0; i < 5; ++i) 
    {
        printf("%s ", *(str_array + i));
    }

    return 0;
}

   

在C++ STL中，提供了sort函数，可以通过指定比较函数来对数组进行排序。比较函数需要返回一个bool类型的值，表示两个元素的比较结果。下面的代码可以对字符串数组按照字典序进行排序：

八、字符串去重的方法

下面我们总结一下字符串去重的五种方法。

1、哈希表法

哈希表法的实现原理是创建一个哈希表，将字符串数组中的每个元素都插入到哈希表中。由于哈希表中不能存在相同的元素，所以最终得到的哈希表中就是去重后的字符串数组。实现语言包括C++,Python等。

2、双重循环法

双重循环法的实现原理是，使用两个循环遍历整个字符串数组，对于每个元素，判断它前面是否已经出现过。如果已经出现过，则标记为重复元素，否则添加到新的数组中。该方法的时间复杂度为O(N^2)。实现语言包括C++,Java等。

3、ES6 Set去重法

ES6中提供了Set数据结构，Set可以自动去重。结合ES6的解构语法，就可以使用一行代码实现字符串数组的去重操作。实现语言为JS。

4、reduce去重法

reduce函数是JS中非常常用的函数，通常用于将一个数组中的元素按照某种方式进行聚合。在去重时，我们可以通过reduce函数来依次遍历数组中的每个元素，将不同的元素保存到res数组中，从而实现去重操作。该方法的时间复杂度为O(N)。实现语言为JS。

5、filter去重法

filter函数通常用于过滤数组中的元素，从而得