8000 add 747 · masiht/Leetcode@fcc61ee · GitHub
[go: up one dir, main page]
Skip to content

Commit fcc61ee

Browse files
fishercoder1534fishercoder1534
committed
add 747
1 parent a1335ae commit fcc61ee

File tree

3 files changed

+113
-0
lines changed

3 files changed

+113
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,7 @@ Your ideas/fixes/algorithms are more than welcome!
2424
|-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
2525
|750|[Number Of Corner Rectangles](https://leetcode.com/problems/number-of-corner-rectangles/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_750.java) | O((m*n)^2) | O(1) | |Medium|
2626
|748|[Shortest Completing Word](https://leetcode.com/problems/shortest-completing-word/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_748.java) | O(n) | O(1) | |Easy|
27+
|747|[Largest Number Greater Than Twice of Others](https://leetcode.com/problems/largest-number-greater-than-twice-of-others/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_747.java) | O(n) | O(1) | |Easy|
2728
|746|[Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_746.java) | O(n) | O(1) | |Easy|
2829
|744|[Find Smallest Letter Greater Than Target](https://leetcode.com/problems/find-smallest-letter-greater-than-target/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_744.java) | O(logn) | O(1) || Easy|
2930
|739|[Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_739.java) | O(n^2) | O(1) | |Medium|

‎src/main/java/com/fishercoder/solutions/_747.java

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.Arrays;
4+
import java.util.HashMap;
5+
import java.util.Map;
6+
7+
/**
8+
* 747. Largest Number Greater Than Twice of Others
9+
*
10+
* In a given integer array nums, there is always exactly one largest element.
11+
* Find whether the largest element in the array is at least twice as much as every other number in the array.
12+
* If it is, return the index of the largest element, otherwise return -1.
13+
14+
Example 1:
15+
Input: nums = [3, 6, 1, 0]
16+
Output: 1
17+
Explanation: 6 is the largest integer, and for every other number in the array x,
18+
6 is more than twice as big as x. The index of value 6 is 1, so we return 1.
19+
20+
Example 2:
21+
Input: nums = [1, 2, 3, 4]
22+
Output: -1
23+
Explanation: 4 isn't at least as big as twice the value of 3, so we return -1.
24+
25+
Note:
26+
nums will have a length in the range [1, 50].
27+
Every nums[i] will be an integer in the range [0, 99].
28+
*/
29+
public class _747 {
30+
31+
public static class Solution1 {
32+
public int dominantIndex(int[] nums) {
33+
Map<Integer, Integer> map = new HashMap<>();
34+
int max;
35+
int secondMax;
36+
for (int i = 0; i < nums.length; i++) {
37+
map.put(nums[i], i);
38+
}
39+
Arrays.sort(nums);
40+
max = nums[nums.length - 1];
41+
secondMax = nums[nums.length - 2];
42+
if (max >= 2 * secondMax) {
43+
return map.get(max);
44+
} else {
45+
return -1;
46+
}
47+
}
48+
}
49+
50+
public static class Solution2 {
51+
public int dominantIndex(int[] nums) {
52+
int max = Integer.MIN_VALUE;
53+
int maxIndex = -1;
54+
for (int i = 0; i < nums.length; i++) {
55+
if (nums[i] > max) {
56+
max = nums[i];
57+
maxIndex = i;
58+
}
59+
}
60+
for (int i = 0; i < nums.length; i++) {
61+
if (nums[i] * 2 > max && i != maxIndex) {
62+
return -1;
63+
}
64+
}
65+
return maxIndex;
66+
}
67+
}
68+
}< 8000 /div>

‎src/test/java/com/fishercoder/_747Test.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._747;
4+
import com.fishercoder.solutions._9;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import static org.junit.Assert.assertEquals;
9+
10+
public class _747Test {
11+
private static _747.Solution1 solution1;
12+
private static _747.Solution2 solution2;
13+
private static int[] nums;
14+
15+
@BeforeClass
16+
public static void setup() {
17+
solution1 = new _747.Solution1();
18+
solution2 = new _747.Solution2();
19+
}
20+
21+
@Test
22+
public void test1() {
23+
nums = new int[] {3, 6, 1, 0};
24+
assertEquals(1, solution1.dominantIndex(nums));
25+
}
26+
27+
@Test
28+
public void test2() {
29+
nums = new int[] {3, 6, 1, 0};
30+
assertEquals(1, solution2.dominantIndex(nums));
31+
}
32+
33+
@Test
34+
public void test3() {
35+
nums = new int[] {1, 2, 3, 4};
36+
assertEquals(-1, solution1.dominantIndex(nums));
37+
}
38+
39+
@Test
40+
public void test4() {
41+
nums = new int[] {1, 2, 3, 4};
42+
assertEquals(-1, solution2.dominantIndex(nums));
43+
}
44+
}

0 commit comments

Comments
 (0)
0