在一个字符串中找到第一个只出现一次的字符

草草草!!!

在数组的符合某种条件的所有元素中找到的最小的元素。

利用选择排序的原理保存最小元素的索引的方法查找最小值,记得!第一个索引设置成符合要求的元素的索引,不要随便设置成数组的第一个元素的索引。

24 -- 38行代码。 

在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。

(1)不使用额外空间,时间复杂度是O(n^2)

像冒泡排序那样,内存循环对外循环判断,比如第一个a,扫描后续元素,有a则不满足。

(2)哈希表。

k = 0; //填写哈希表时,每次设置成1就++k 
typedef struct {
    int flag;//初始化为0,第一次扫描到设置成1,再扫描到设置成2 
    int order;//初始化266,第几个设置成1的就设置成,几 
};//哈希表的结点

扫描完字符串后,就扫描哈希表:if(flag == 1 && a[ i ].order < 当前最小order索引值 )  就更新索引值。

时间复杂度是: 255 + 255 + n + 255 = O(n)

 1 typedef struct {
 2     int flag;//初始化成0,第一次出现设置成 1,再出现设置成2 
 3     int order; //初始化成0,第几次设置成1,就设置成几 
 4 }Node;
 5 char Search(char *str) {
 6     int k = 0;
 7     if(str == NULL) exit(-1);
 8     Node arr[128];
 9     for(int i = 0;i < 128; ++i) {
10         arr[i].flag = 0;
11         arr[i].order = 200;//任意大于128的整数 
12     }
13     
14     char *p = str;
15     for(;*p!='';++p) {
16         if(arr[*p].flag == 0) {
17             arr[*p].flag = 1;
18             arr[*p].order = k++;
19         }
20         else {
21             arr[*p].flag = 2;
22         }
23     }
24     int first;
25     int start = 0;
26     for(int i = 0; i < 128; ++i) {
27         if(start == 0) {
28             if(arr[i].flag == 1) {
29                first = i;
30                start = 1;
31             }
32         }    
33         else {
34             if(arr[i].flag == 1 && arr[i].order < arr[first].order)
35             first = i;
36         }
37     }
38     return first;
39 }
原文地址:https://www.cnblogs.com/joyeehe/p/7943548.html