Hướng dẫn count duplicate elements hackerrank solution javascript - đếm các phần tử trùng lặp giải pháp hackerrank javascript

Đã hỏi 4 năm, 2 tháng trước 4 years, 2 months ago

Đã xem 42k lần 42k times

\ $ \ beingroup \ $

Đây thực sự là một câu hỏi phỏng vấn hackerrank tôi đã giải quyết nhưng tôi cần hướng dẫn về cách tối ưu hóa nó cho

1. Thời gian
2. Không gian

Đưa ra một loạt các số nguyên, nhiệm vụ của bạn là đếm số lượng các phần tử mảng trùng lặp. Trùng lặp được định nghĩa là hai hoặc nhiều yếu tố giống hệt nhau. Ví dụ, trong mảng [1, 2, 2, 3, 3, 3], hai twos là một bản sao và ba phần ba cũng vậy.

Mô tả chức năng

Hoàn thành chức năng countDuplicates trong trình chỉnh sửa bên dưới. Hàm phải trả về một số nguyên biểu thị số lượng các giá trị không duy nhất (sao chép) trong mảng số.

countDuplicates có (các) tham số sau:

numbers[numbers[0],...numbers[n-1]]: Một loạt các số nguyên để xử lý

Hạn chế

1 ≤ n ≤ 1000 1 ≤ số [i] 1000, 0 i 1 ≤ numbers[i] ≤ 1000, 0 ≤ i < n

Đầu vào mẫu: [1, 3, 1, 4, 5, 6, 3, 2] Đầu ra mẫu: 2 Giải thích: Các số nguyên 1 và 3 cả hai đều xảy ra nhiều lần, vì vậy chúng tôi trả về 2 như câu trả lời của chúng tôi.
Sample Output: 2
Explanation: The integers 1 and 3 both occur more than once, so we return 2 as our answer.

function countDuplicates(original) {

  let counts = {},
    duplicate = 0;
  original.forEach(function(x) {
    counts[x] = (counts[x] || 0) + 1;
  });

  for (var key in counts) {
    if (counts.hasOwnProperty(key)) {
      counts[key] > 1 ? duplicate++ : duplicate;
    }
  }

  return duplicate;

}

200_success

Phù bằng vàng 143K2222 gold badges185 silver badges469 bronze badges

Hỏi ngày 4 tháng 9 năm 2018 lúc 13:26Sep 4, 2018 at 13:26

\ $ \ endgroup \ $

1

\ $ \ beingroup \ $

Đây thực sự là một câu hỏi phỏng vấn hackerrank tôi đã giải quyết nhưng tôi cần hướng dẫn về cách tối ưu hóa nó cho

Thời gian

Không gian

function countDuplicates(original) {
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
      uniqueItems.delete(value);
    } else {
      uniqueItems.add(value);
    }
  }
  return duplicates.size;
}



/* Test code not related to solution */
function test(name, func, data, result) {
  const output =  `${name} [${data.join(", ")}] : `;
  console.log(output + (func(data) === result ? "passed" : "failed")); 
}


test("1 duplicate ", countDuplicates, [9, 11, 12, 2, 7, 4, 2], 1);
test("1 duplicate ", countDuplicates, [6, 6, 6], 1);
test("2 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2], 2);
test("3 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2, 0], 3);
test("No duplicates ", countDuplicates, [0, 1, 4, 2, 7, 5, 8, 9], 0);

Đưa ra một loạt các số nguyên, nhiệm vụ của bạn là đếm số lượng các phần tử mảng trùng lặp. Trùng lặp được định nghĩa là hai hoặc nhiều yếu tố giống hệt nhau. Ví dụ, trong mảng [1, 2, 2, 3, 3, 3], hai twos là một bản sao và ba phần ba cũng vậy.

Mô tả chức năng

function countDuplicatesMemory(original) {
  var maxSize = 0;
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
      maxSize = Math.max(maxSize, duplicates.size + uniqueItems.size);
      uniqueItems.delete(value);
    } else {
      uniqueItems.add(value);
      maxSize = Math.max(maxSize, duplicates.size + uniqueItems.size);
    }
  }
  return maxSize;
}



var memoryUse = 0;
var min = Infinity;
var max = 0;
const cycles = 10000;
const arraySize = 1000;
const maxRange = 10000;

for(let i = 0; i < cycles; i++){
  const arr = [];
  const range = Math.random() * maxRange | 0;
  for(let i = 0; i < arraySize; i++){
     arr.push(Math.random() * range | 0);
  }
  const mem = countDuplicatesMemory(arr);
  memoryUse += mem;
  min = Math.min(mem, min);
  max = Math.max(mem, max);
}
console.log("Mean memory use O(n * " + (memoryUse / cycles / arraySize).toFixed(3)+ ")");
console.log("Min memory use  O(n * " + (min / arraySize).toFixed(3)+ ")");
console.log("Max memory use  O(n * " + (max / arraySize).toFixed(3)+ ")");

Hoàn thành chức năng countDuplicates trong trình chỉnh sửa bên dưới. Hàm phải trả về một số nguyên biểu thị số lượng các giá trị không duy nhất (sao chép) trong mảng số.

countDuplicates có (các) tham số sau:

numbers[numbers[0],...numbers[n-1]]: Một loạt các số nguyên để xử lýSep 4, 2018 at 15:50

Blindman67Blindman67Blindman67

Hạn chế2 gold badges12 silver badges39 bronze badges

\ $ \ endgroup \ $

6