Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher’s h-index.
According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
Example 1:
Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.
Example 2:
Input: citations = [1,3,1]
Output: 1
Constraints:
n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000
Version 1
public class Solution {
public int HIndex(int[] citations)
{
var length = citations.Length;
var index = 0;
for (int i = 1; i <= length ; i++)
{
var count = citations.Count(a=>a>=i);
if (count >= i && i > index)
index = i;
}
return index;
}
}
//testing Code
H_Index _indexer = new H_Index();
[Test]
public void Test001()
{
_indexer.HIndex(new int []{3, 0, 6, 1, 5}).Should().Be(3);
}
[Test]
public void Test002()
{
_indexer.HIndex(new int []{1, 3, 1}).Should().Be(1);
}
public static void QuickSortAlgorithm(int[] arr, int left, int right)
{
if (left < right)
{
int partitionIndex = Partition(arr, left, right);
QuickSortAlgorithm(arr, left, partitionIndex - 1);
QuickSortAlgorithm(arr, partitionIndex + 1, right);
}
}
private static int Partition(int[] arr, int left, int right)
{
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++)
{
if (arr[j] < pivot)
{
i++;
Swap(arr, i, j);
}
}
Swap(arr, i + 1, right);
return i + 1;
}
private static void Swap(int[] arr, int i, int j)
{
(arr[i], arr[j]) = (arr[j], arr[i]);
}
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Constraints:
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
Follow-up: Could you solve the problem in linear time and in O(1) space?
我的第一版本:
public class Solution {
public int MajorityElement(int[] nums) {
if (nums.Length == 1)
return nums[0];
var max = nums.Length / 2;
var result = 0;
Dictionary<int, int> counter = new Dictionary<int, int>();
foreach(var n in nums)
{
if (counter.ContainsKey(n))
{
counter[n]++;
if (counter[n] > max)
{
max = counter[n];
result = n;
}
}
else
{
counter.Add(n, 1);
}
}
return result;
}
}
public class Solution
{
public int MajorityElement(int[] nums)
=>nums.GroupBy(x => x).Select(x => new { x.Key, c = x.Count()}).OrderByDescending(x => x.c).FirstOrDefault().Key;
}
寫法2
public class Solution {
public int MajorityElement(int[] nums) {
//return nums.ToList().GroupBy(x => x).OrderByDescending(g=>g.Count()).Select(y=>y.Key).FirstOrDefault();
Array.Sort(nums);
return nums[nums.Length/2];
}
}
Time complexity: O(nlog(n))
Space complexity: No extra space is used
最想瞭解:
public class Solution {
public int MajorityElement(int[] nums) {
int count = 0;
int? candidate = null;
foreach (int num in nums) {
if (count == 0) candidate = num;
count += (num == candidate) ? 1 : -1;
}
return candidate.Value;
}
}
Time complexity: O(n)
Space complexity: O(1)
ChatGPT版本
using System;
class Program
{
static int MajorityElement(int[] nums)
{
int count = 0;
int candidate = 0;
foreach (int num in nums)
{
if (count == 0)
candidate = num;
if (num == candidate)
count++;
else
count--;
}
return candidate;
}
static void Main(string[] args)
{
int[] nums = { 2, 2, 1, 1, 1, 2, 2 };
int majority = MajorityElement(nums);
Console.WriteLine("Majority element: " + majority);
}
}
說明如下: Boyer-Moore投票算法(Boyer-Moore Voting Algorithm)是一種用於在一個具有大量元素的列表中查找多數元素的有效方法。該算法的時間複雜度為O(n),其中n是列表的大小。該算法是由Robert S. Boyer和J Strother Moore於1981年提出的。
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
直覺寫法
public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
var merged = nums1.Concat(nums2);
var mergedArray = merged.OrderBy(a => a).ToArray();
if (mergedArray.Length % 2 > 0)
{
var median = mergedArray[(mergedArray.Length - 1) / 2];
return median;
}
else
{
var medianFirst = mergedArray[((mergedArray.Length) / 2)-1];
var medianLast = mergedArray[((mergedArray.Length) / 2)];
return ((double)medianFirst + (double)medianLast) / 2;
}
}
}
結果就這樣過了,到底為什麼是Hard?
看了某些人也是這樣寫 Complexity: Time complexity: The time complexity is dominated by the sorting operation, which takes O(N log N) time, where N is the total number of elements in nums1 and nums2. Space complexity: The space complexity is determined by the size of the combined list nums, which is O(N), where N is the total number of elements in nums1 and nums2.
LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
using System;
using System.Collections.Generic;
using System.Linq;
namespace LeetCode2023_Paul.LRUCacheV1;
public class LRUCacheV2
{
private int _capacity;
private List<int> _keys;
private Dictionary<int, int> _cache;
public LRUCacheV2(int capacity)
{
_keys = new List<int>();
_cache = new Dictionary<int, int>();
_capacity = capacity;
}
public int Get(int key)
{
var value = -1;
if (_cache.ContainsKey(key))
{
value = _cache[key];
//有被抓到的key重新 add到後面,實現愈少用到的key會浮在第一個
_keys.Remove(key);
_keys.Add(key);
}
return value;
}
public void Put(int key, int value) {
if (_cache.ContainsKey(key))
{
_keys.Remove(key);
_keys.Add(key);
_cache[key] = value;
}
else
{
if (_cache.Keys.Count == _capacity)
{
//因為最少用到的Key總是在第一個,所以cache數滿了的話,就移掉第一個(這邊跟NodeList不太一樣,但是利用List的特性可以作一樣效果
//LRU的意思就是Least Recently Used, 相反則是LFU Frequently Used
var lruKey = _keys.FirstOrDefault();
_keys.Remove(lruKey);
_cache.Remove(lruKey);
}
_keys.Add(key);
_cache.Add(key, value);
}
}
}