Re: [閒聊] 每日leetcode
https://leetcode.com/problems/minimum-index-of-a-valid-split
2780. Minimum Index of a Valid Split
給你一個陣列，有一個數字x在這個陣列出現超過一半次，求出你是否可以找到一個i
將該陣列切成[0:i][i+1:n]兩個子陣列，且x在兩個子陣列都出現超過一半次，如果有
多種切法返回i最小的切法。
思路:
1.先找出x是哪個數字和共有幾個。
2.從左邊到右邊一個一個把數字加入到左邊陣列，然後用當前有幾個x去判斷左邊和右邊
的x數量是否都有超出子陣列長度的二分之一。
Java Code:
------------------------------------------------
class Solution {
public int minimumIndex(List<Integer> nums) {
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
int x = 0;
int countOfX = 0;
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
if (entry.getValue() > countOfX) {
x = entry.getKey();
countOfX = entry.getValue();
}
}
int currXCount = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums.get(i) == x) {
currXCount++;
}
int leftSize = i + 1;
int rightSize = nums.size() - i - 1;
if (currXCount * 2 > leftSize && (countOfX - currXCount) * 2 >
rightSize) {
return i;
}
}
return -1;
}
}
------------------------------------------------
--
https://i.imgur.com/5xKbxoh.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1743096073.A.638.html
※ 編輯: Rushia (49.158.101.161 臺灣), 03/28/2025 01:21:58
討論串 (同標題文章)
完整討論串 (本文為第 1374 之 1548 篇)：