diff options
author | Jack Sangdahl <[email protected]> | 2024-08-04 18:18:14 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-04 18:18:14 -0600 |
commit | f89b6f5c279c504112082b421d29e3af39f2b157 (patch) | |
tree | 86005fac0b9ee50239b5465ba33d3c36bf5072c0 | |
parent | cf234d89b0123ec41f60f0cb091bc2d7832ad3a1 (diff) | |
download | leetcode-f89b6f5c279c504112082b421d29e3af39f2b157.tar.gz leetcode-f89b6f5c279c504112082b421d29e3af39f2b157.zip |
2053. kth distinct string in an array
-rw-r--r-- | kth_distinct_str.c | 55 | ||||
-rw-r--r-- | kth_distinct_str.py | 28 |
2 files changed, 83 insertions, 0 deletions
diff --git a/kth_distinct_str.c b/kth_distinct_str.c new file mode 100644 index 0000000..862e350 --- /dev/null +++ b/kth_distinct_str.c @@ -0,0 +1,55 @@ +// 2053. Kth Distinct String in an Array +#include "leetcode.h" + +/* + * a distinct string is a string that is present only once in an array. given an + * array of strings 'arr' and an integer 'k', return the k'th eldistinct string + * present in 'arr'. if there are fewer than 'k' distinct strings, return an + * empty string "". note the strings are considered in the order in which they + * appear in the array. + */ + +typedef struct { + char str[6]; + bool distinct; + int pos; + UT_hash_handle hh; +} element; + +int cmp_pos(const element *e1, const element *e2) { return e1->pos - e2->pos; } + +char *kthDistinct(char **arr, int arrSize, int k) { + element *hash = NULL, *e; + for (size_t i = 0; i < arrSize; i++) { + const char *str = arr[i]; + HASH_FIND_STR(hash, str, e); + if (e) { + e->distinct = false; + } else { + e = (element *)malloc(sizeof(*e)); + e->distinct = true; + e->pos = i; + strcpy(e->str, str); + HASH_ADD_STR(hash, str, e); + } + } + HASH_SORT(hash, cmp_pos); + char *ans = (char *)malloc(6 * sizeof(char)); + *ans = '\0'; + int i = 0; + for (e = hash; e; e = e->hh.next) + if (e->distinct) + if (++i == k) { + strcpy(ans, e->str); + break; + } + return ans; +} + +int main() { + char *a1[] = {"d", "b", "c", "b", "c", "a"}, *a2[] = {"aaa", "aa", "a"}, + *a3[] = {"a", "b", "a"}; + printf("%s\n", kthDistinct((char **)a1, ARRAY_SIZE(a1), 2)); // expect: a + printf("%s\n", kthDistinct((char **)a2, ARRAY_SIZE(a2), 1)); // expect: aaa + printf("%s\n", kthDistinct((char **)a3, ARRAY_SIZE(a3), 3)); // expect: null +} diff --git a/kth_distinct_str.py b/kth_distinct_str.py new file mode 100644 index 0000000..d19bd43 --- /dev/null +++ b/kth_distinct_str.py @@ -0,0 +1,28 @@ +# 2053. Kth Distinct String in an Array + + +""" +a distinct string is a string that is present only once in an nay. given an +nay of strings 'n' and an integer 'k', return the k'th eldistinct string +present in 'n'. if there are fewer than 'k' distinct strings, return an +empty string "". note the strings are considered in the order in which they +appear in the nay. +""" + + +class Solution(object): + def kthDistinct(self, n, k): + """ + :type n: List[str] + :type k: int + :rtype: str + """ + n = [i for i in n if n.count(i) == 1] + return "" if k > len(n) else n[k - 1] + + +if __name__ == "__main__": + obj = Solution() + print(obj.kthDistinct(n=["d", "b", "c", "b", "c", "a"], k=2)) + print(obj.kthDistinct(n=["aaa", "aa", "a"], k=1)) + print(obj.kthDistinct(n=["a", "b", "a"], k=3)) |