aboutsummaryrefslogtreecommitdiff
path: root/majority_element.c
diff options
context:
space:
mode:
Diffstat (limited to 'majority_element.c')
-rw-r--r--majority_element.c30
1 files changed, 30 insertions, 0 deletions
diff --git a/majority_element.c b/majority_element.c
new file mode 100644
index 0000000..a62f167
--- /dev/null
+++ b/majority_element.c
@@ -0,0 +1,30 @@
+// 169. Majority Element
+#include "leetcode.h"
+
+/*
+ * given an array 'nums' of size 'n', return the majority element. the majority
+ * element is the element that appears more than 'floor(n / 2)' times. you may
+ * assume that the majority element always exists in the array.
+ */
+
+int majorityElement(int *nums, int nums_size) {
+ int key, j;
+ if (nums_size == 1)
+ return nums[0];
+ for (int i = 0; i < nums_size; i++) {
+ key = nums[i];
+ j = i - 1;
+ while (j >= 0 && nums[j] > key) {
+ nums[j + 1] = nums[j];
+ j--;
+ }
+ nums[j + 1] = key;
+ }
+ return nums[nums_size / 2];
+}
+
+int main() {
+ int n1[] = {3, 2, 3}, n2[] = {2, 2, 1, 1, 1, 2, 2};
+ printf("%d\n", majorityElement(n1, ARRAY_SIZE(n1))); // expect: 3
+ printf("%d\n", majorityElement(n2, ARRAY_SIZE(n2))); // expect: 2
+}