goctave · April 16, 2012 03:10 · Apr 16, 2012
diff --git a/1.c b/1.c
@@ -0,0 +1,68 @@
+/**************************************************
+1.最简单的方法就是两层循环，复杂度O(n^2)
+2.使用排序，然后找重复。复杂度为O(nlgn)+O(n)=O(nlgn)
+3.直接使用快排，在排序过程中，如果发现有重复的，立即结束递归
+****************************************************/
+
+#include <stdio.h>
+#include <string.h>
+
+int repeat;
+
+/* exchange two char */
+void swap(char *a, char *b)
+{
+	char temp;
+	temp = *a;
+	*a = *b;
+	*b = temp;
+}
+
+/* quick sort */
+void qsort(char str[], int p, int r)
+{
+	if(p < r)
+	{
+		int q = partition(str, p, r);
+		if(q == -1)
+			return;
+		qsort(str, p, q - 1);
+		qsort(str, q + 1, r);
+	}
+}
+
+/* partition */
+int partition(char str[], int p, int r)
+{
+	char ch = str[r];
+	int i = p - 1;
+	int j;
+	for(j = p; j < r; j++)
+	{
+		if(str[j] == ch) /* find a same char, return */
+		{
+			repeat = 1;
+			return -1;
+		}
+		else if(str[j] < ch)
+		{
+			i++;
+			swap(&str[i], &str[j]);
+		}
+	}
+	swap(&str[i + 1], &str[r]);
+	return i + 1;
+}
+
+int main()
+{
+	char str[100];
+	scanf("%s", str);
+	repeat = 0;
+	qsort(str, 0, strlen(str) - 1);
+	if(repeat)
+		printf("Yes\n");
+	else
+		printf("No\n");
+	return 0;
+}