一苍姜、哈希算法
在一個字符串中找到第一個只出現(xiàn)一次的字符译蒂。例如：輸入“abaccdeff”輸出b曼月。
思路：考察hash的使用，利用每個字母的ASCII碼作hash來作為數組的index柔昼。使用一個數組存儲每個字母出現(xiàn)的次數哑芹，數組記錄的內容是該字母出現(xiàn)的次數，最終遍歷字符串捕透，找到第一個數組內容為1的字母即可聪姿。時間復雜度為O(n)。
char findFirstChar(char *cha) {
char result = '\0';
// 用于存放每個字符出現(xiàn)的次數乙嘀，下標為字符的ASCII值
int array[256] = {0};
char *p = cha;
// 遍歷字符串末购，根據ASCII值存入數組中
while (*p != '\0') {
// 字符對應的存儲位置，進行次數+1操作虎谢。
array[*(p++)]++;
}
//重置p指針
p = cha;
while (*p != '\0') {
// 遇到第一個出現(xiàn)次數為1的字符盟榴，打印出結果。
if (array[*p] == 1) {
result = *p;
break;
}
p++;
}
return result;
}
測試代碼：
void hash_findFirstCharTest() {
char *cha = "gabaccdeff";
char fc = findFirstChar(cha);
printf("this char is %c \n", fc);
}
輸出結果：
this char is g
二婴噩、 查找兩個子視圖的共同父視圖
思路：記錄視圖A的所有父視圖存放到數組A擎场。將視圖B的所有父視圖存放到數組B。然后倒序比較兩個數組中的視圖几莽，當比較到第一個不一樣時迅办，之前找到的就是所有共同父視圖。
示例代碼：
- (NSArray<NSView *> *)findCommonSuperView:(NSView *)view other:(NSView *)viewOther {
// 結果數組
NSMutableArray *result = [NSMutableArray array];
// 兩個子視圖所有父視圖組成的數組章蚣。
NSArray *aSuperViews = [self findSuperView:view];
NSArray *bSuperViews = [self findSuperView:viewOther];
int i = 0;
// 越界條件選取小的那個
while (i < MIN(aSuperViews.count, bSuperViews.count)) {
NSView *aSuperView = [aSuperViews objectAtIndex:aSuperViews.count - i - 1];
NSView *bSuperView = [bSuperViews objectAtIndex:bSuperViews.count - i - 1];
// 比較是否相等站欺，相等則為共同父視圖。不相等結束遍歷纤垂。
if (aSuperView == bSuperView) {
[result addObject:aSuperView];
i++;
} else {
break;
}
}
return result;
}
- (NSArray <NSView *> *)findSuperView:(NSView *)view {
// 第一個父視圖
NSView *temp = view.superview;
NSMutableArray *result = [NSMutableArray array];
while (temp) {
[result addObject:temp];
temp = temp.superview;
}
return result;
}
注意引入的是
AppKit所以視圖為NSView矾策。
三、無序數組中的中位數洒忧。
方案：排序算法 + 中位數蝴韭；利用快排思路（分治思想）。
關于排序算法這里不再贅述熙侍，可以網上搜索榄鉴。
中位數：當n為奇數時履磨，（n + 1)/2 ;當n為偶數時，（n / 2 + (n / 2 + 1）/ 2庆尘。
思路：快排思想剃诅。任意選擇一個元素，以該元素為支點劃分數組為兩部分驶忌，如果左側集合長度恰好為（n -1)/2矛辕，那么支點就是中位數。如果左側長度小于（n - 1)/2付魔，那么中位數在右側聊品，否則中位數在左側。
示例代碼：
// 無序數組的中位數
int findMedian(int a[], int aLen) {
int low = 0;
int high = aLen - 1;
// 中位下標
int mid = (aLen - 1) / 2;
// 第一遍快排
int div = PartSort(a, low, high);
while (div != mid) {
if (mid < div) {
// 左半區(qū)間
div = PartSort(a, low, div - 1); // 遞歸
} else {
//右半區(qū)間
div = PartSort(a, div + 1, high); // 遞歸
}
}
return a[mid];
}
int PartSort(int a[], int start, int end) {
// 兩個哨兵
int low = start;
int high = end;
// 關鍵數
int key = a[end];
while (low < high) {
// 左邊的值要比Key小
while (low < high && a[low] <= key) {
++low;
}
// 右邊的值要比Key大
while (low < high && a[high] >= key) {
--high;
}
// 交換兩個哨兵對應的值
if (low < high) {
int temp = a[low];
a[low] = a[high];
a[high] = temp;
}
}
// 交換關鍵數
int temp = a[high];
a[high] = a[end];
a[end] = temp;
return low;
}
測試代碼：
void findMedianTest() {
int list[9] = {12,3,10,8,6,7,11,13,9};
// 3 6 7 8 9 10 11 12 13
// ^
int median = findMedian(list, 9);
printf("the median is %d \n", median);
}
輸出結果：
the median is 9
小結
示例代碼倉庫地址：Algorithm
