33
loading...
[DataStructure&Algorithm] 2. Array
Inside a computer, there are chips called RAM, random-access memory. A RAM stores data for short-term use. Hard drive and SSD can be used for long-term storage but they are slower than RAM. RAM is considerably faster, but it requires power to keep data stored since it is volatile.
We can store variables back to back in memory and access them with loops. A collection of items stored at contiguous memory locations is called an array. Each item stored in an array is called an element, and each location of an element in an array is called an index. We can use indexes to identify the element, because every array starts with index 0.
Many languages have their own ways to declare an array.
// c
int arrayName[5] = {25, 5, 35, 1, 6};// java
int[] arrayName = {25, 5, 35, 1, 6};# python
array_name = [25, 5, 35, 1, 6]// javascript
let arrayName = [25, 5, 35, 1, 6];# python
def solution(a, n):
answer = 0
for i in range(n):
answer += a[i] * i
prev_result, total_sum = answer, sum(a)
for i in range(n-1):
result = prev_result - total_sum + a[i] * n
if result > answer:
answer = result
prev_result = result
return answer
# Execution Time:0.71// java
class Solution {
int max_sum(int arr[], int n) {
int answer = 0;
for (int i = 0; i < n; i++) {
answer += (arr[i] * i);
}
int prevResult = answer;
int totalSum = 0;
for (int i = 0; i < n; i++) {
totalSum += arr[i];
}
for (int j = 0; j < n - 1; j++) {
int result = prevResult - totalSum + arr[j] * n;
if (result > answer) {
answer = result;
}
prevResult = result;
}
return answer;
}
}
// Execution Time:1.96# python
def solution(arr, n):
li = [x for x in arr if x > 0]
li = sorted(list(set(li)))
for i in range(0, len(li)):
if i+1 != li[i]:
return i+1
return (li[-1]+1 if len(li) > 0 else 1)
# Execution Time:0.96// java
import java.util.Arrays;
class Solution{
static int missingNumber(int arr[], int size) {
int answer = 0;
int newarr[] = new int[size + 1];
for (int k = 0; k < size; k++)
newarr[k] = arr[k];
newarr[size] = 0;
Arrays.sort(newarr);
if (size == 1) {
answer = 1;
} else {
for (int i = 0; i < size; i++) {
if (newarr[i] < 0) {
continue;
}
if (newarr[i + 1] - newarr[i] > 1) {
answer = newarr[i] + 1;
break;
}
}
}
if (answer == 0) {
answer = newarr[size] + 1;
}
return answer;
}
}
// Execution Time:3.16# python
def solution(arr, n):
for i in range(n-1,-1,-1):
for j in range(n-i):
if arr[j] <= arr[j+i]:
return i
# Execution Time:0.51// java
class Solution{
static int maxIndexDiff(int arr[], int n) {
int answer = 0;
for (int i=n-1; i>=0; i--) {
for (int j=0; j<n-i; j++) {
if(arr[j] <= arr[j+i]) {
answer = i;
break;
}
}
if (answer != 0) {
break;
}
}
return answer;
}
}
// Execution Time:0.61# python
def solution(arr, n):
a,b,diff = 0,0,0
arr.sort()
for i in range(n):
if a != 0 and b != 0:
break
current_diff = i + 1 - arr[i]
if current_diff != diff:
if current_diff > diff and a == 0:
a = arr[i]
elif b == 0:
b = i + 1 - diff
diff = current_diff
if b == 0:
b = arr[-1] + 1
return [a, b]
# Execution Time:0.42// java
class Solution {
int[] findTwoElement(int arr[], int n) {
// code here
int repeating = 0;
int missing = 0;
int diff = 0;
int current_diff = 0;
Arrays.sort(arr);
for (int i = 0; i < n; i++) {
if (repeating != 0 & missing != 0) {
break;
}
current_diff = i + 1 - arr[i];
if (current_diff != diff) {
if (current_diff > diff & repeating == 0) {
repeating = arr[i];
} else if (missing == 0) {
missing = i + 1 - diff;
}
diff = current_diff;
}
}
if (missing == 0) {
missing = arr[n-1] + 1;
}
int[] answer = {repeating, missing};
return answer;
}
}
// Execution Time:0.76# python
def solution(arr, n):
answer = False
left_sum = 0
right_sum = sum(arr[1:])
for i in range(1, n):
left_sum += arr[i-1]
right_sum -= arr[i]
if left_sum == right_sum:
return 'YES'
if left_sum > right_sum:
return 'NO'
# Execution Time:0.23// java
class Solution {
String equilibrium(int arr[], int n) {
// code here
int leftSum = 0;
int rightSum = 0;
String answer = null;
for (int i = 1; i < n; i++) {
rightSum += arr[i];
}
for (int i = 1; i < n; i++) {
leftSum += arr[i - 1];
rightSum -= arr[i];
if (leftSum == rightSum) {
answer = "YES";
break;
}
if (leftSum > rightSum) {
answer = "NO";
break;
}
}
return answer;
}
}
// Execution Time:0.5433